> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/data-structure/heap.md).

# 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
// Java 
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
```

(2) Self Defined Heap

```java
// 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, ](https://leetcode.com/problems/sort-characters-by-frequency/?tab=Description%29\[Kth%20Smallest%20Element%20in%20a%20Sorted%20Matrix]%28https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/?tab=Description%29,%20\[Kth%20Largest%20Element%20in%20an%20Array,%20]%28https://leetcode.com/problems/kth-largest-element-in-an-array/?tab=Description%29\[Super%20Ugly%20Number]%28https://leetcode.com/problems/super-ugly-number/?tab=Description%29,%20\[Ugly%20Number%20II,%20]%28https://leetcode.com/problems/ugly-number-ii/?tab=Description%29%20\[Find%20K%20Pairs%20with%20Smallest%20Sums,%20]%28https://leetcode.com/problems/find-k-pairs-with-smallest-sums/?tab=Description%29\[Merge%20k%20Sorted%20Lists]%28https://leetcode.com/problems/merge-k-sorted-lists/?tab=Description%29,%20\[IPO]%28https://leetcode.com/problems/ipo/?tab=Description)[Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/?tab=Description), [Find K Pairs with Smallest Sums](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/?tab=Description), [Super Ugly Number, ](https://leetcode.com/problems/super-ugly-number/?tab=Description)[Ugly Number II](https://leetcode.com/problems/ugly-number-ii/?tab=Description), [IPO, ](https://leetcode.com/problems/ipo/?tab=Description)[Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/?tab=Description), [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/?tab=Description)
2. Top k largest/smallest: [Find Median from Data Stream, ](https://leetcode.com/problems/find-median-from-data-stream/?tab=Description%29\[Top%20K%20Frequent%20Elements]%28https://leetcode.com/problems/top-k-frequent-elements/?tab=Description%29,%20\[Sliding%20Window%20Maximum]%28https://leetcode.com/problems/sliding-window-maximum/?tab=Description)[Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/?tab=Description), [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/?tab=Description)
3. Scan line: [The Skyline Problem](https://leetcode.com/problems/the-skyline-problem/?tab=Description%29,%20\[Meeting%20Rooms%20II]%28https://leetcode.com/problems/meeting-rooms-ii/?tab=Description), [Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/?tab=Description)