Heap

Heap

1. Introduction

Heap is a complete binary tree. It is useful for :

(1) Sorting element in the heap (Heap sort, not statble)

(2) Find the top k largest/smallest problem(minHeap stores top k largest, while maxHeap store top k smallest)

2. Construction

(1) MinHeap/ MaxHeap

// Java 
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

(2) Self Defined Heap

// Use lamda expression in Java 8
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

// Use comparator before Java 8
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>(){
    @Override
    public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
        return entry2.getValue() - entry1.getValue();
    }
});

3. Time & Space Complexity

Insertion: O(logn), where n is the number of elements in the heap

Deletion: O(logn)

GetMIn/GetMax: O(1)

4. Question

1. Heap sort: Sort Characters By Frequency, Kth Smallest Element in a Sorted Matrix, Find K Pairs with Smallest Sums, Super Ugly Number, Ugly Number II, IPO, Kth Largest Element in an Array, Merge k Sorted Lists

2. Top k largest/smallest: Find Median from Data Stream, Top K Frequent Elements, Sliding Window Maximum

3. Scan line: The Skyline Problem, Meeting Rooms II