Java: faster solution with DIM Heap instead of java priority queue


  • 2
    B

    The solution with Java PriorityQueue is actually O(n ^2). This is because of the PriorityQueue.remove() method. It actually scans the whole underline queue array to search for the index of the item and to remove it, so it is an O(N) operation. We could make this O(lgn) by writing our own Heap class.

    By using Priority queue, the solution below spends about 1164 ms; with a DIM Heap, it uses about 716 ms.

    getSkyline(), we could replace the Heap with a PriorityQueue

    public List<int[]> getSkyline(int[][] buildings) {
        List<Point> list = new ArrayList<>();
        for(int[] building: buildings){
            list.add(new Point(building[0], building[2], true));
            list.add(new Point(building[1], building[2], false));
        }
        list.sort((p1, p2) -> {
            if(p1.loc != p2.loc)
                return p1.loc - p2.loc;
            if(p1.isLeft != p2.isLeft)
                return p1.isLeft ? 1 : -1;
            return p1.height - p2.height;
        });
        
        LinkedList<int[]> result = new LinkedList<>();
        Heap heap = new Heap();
        for(Point p: list){
            int[] toAdd = null;
            if(p.isLeft){
                if(heap.isEmpty() || p.height > heap.peek())
                    toAdd = new int[]{p.loc, p.height};
                heap.offer(p.height);
            }else{
                heap.remove(p.height);
                if(heap.isEmpty())
                    toAdd = new int[]{p.loc, 0};
                else if(p.height > heap.peek())
                    toAdd = new int[]{p.loc, heap.peek()};
            }
            if(toAdd == null)
                continue;
            if(!result.isEmpty() && toAdd[0] == result.getLast()[0])
                result.removeLast();
            if(result.isEmpty() || toAdd[1] != result.getLast()[1]){
                result.add(toAdd);
            }
        }
        return result;
    }
    

    DIM Heap

    private static class Heap{
        private static class Item{
            int key, count = 1;
    
            public Item(int key) {
                this.key = key;
            }
        }
        
        private Item[] arr = new Item[10100];
        private Map<Integer, Integer> map = new HashMap<>();
        private int size = 0;
        
        private int leftChild(int ind){
            return ind * 2 + 1;
        }
        
        private int rightChild(int ind){
            return ind * 2 + 2;
        }
        
        private boolean hasLeftChild(int ind){
            return leftChild(ind) < size;
        }
        
        private boolean hasRightChild(int ind){
            return rightChild(ind) < size;
        }
    
        private int parent(int ind){
            return (ind - 1) / 2;
        }
        
        private void swap(int i1, int i2) {
            Item tmp = arr[i1];
            arr[i1]  = arr[i2];
            arr[i2]  = tmp;
         }
        
        private void siftDown(int ind){
            while(hasLeftChild(ind)){
                int child = leftChild(ind);
                if(hasRightChild(ind) && arr[child + 1].key > arr[child].key)
                    child++; // compare with right child now
                if(arr[ind].key >= arr[child].key)
                    break;
                map.put(arr[child].key, ind);
                swap(ind, child);
                ind = child;
            }
            map.put(arr[ind].key, ind);
        }
        
        private void siftUp(int ind){
            while(ind > 0){
                int parent = parent(ind);
                if(arr[ind].key <= arr[parent].key)
                    break;
                map.put(arr[parent].key, ind);
                swap(ind, parent);
                ind = parent;
            }
            map.put(arr[ind].key, ind);
        }
        
        void offer(int key){
            if(map.containsKey(key))
                arr[map.get(key)].count++;
            else{
                arr[size++] = new Item(key);
                siftUp(size - 1);
            }
        }
        
        void remove(int key){
            if(!map.containsKey(key))
                return;
            int ind = map.get(key);
            arr[ind].count--;
            if(arr[ind].count == 0){
                map.remove(key);
                size--;
                if(ind == size)
                    return;
                swap(ind, size);
                if(ind > 0 && arr[ind].key > arr[parent(ind)].key)
                    siftUp(ind);
                else
                    siftDown(ind);
            }
        }
        
        boolean isEmpty(){
            return size == 0;
        }
        
        int peek(){
            return arr[0].key;
        }
    }
    

    Utility Point class

    private static class Point{
        int loc, height;
        boolean isLeft;
        public Point(int loc, int height, boolean isLeft) {
            super();
            this.loc = loc;
            this.height = height;
            this.isLeft = isLeft;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.