定义：Heap is a binary tree with two special properties: it must have all its nodes in specific order and its shape must be complete.
注意：
Keep in mind
- We can have duplicate values in a heap — there’s no restriction against that.
- A heap doesn’t follow the rules of a binary search tree; unlike binary search trees, the left node does not have to be smaller than the right node! The ordering of the child nodes isn’t important for a heap; the only ordering that matters is the heap-order property, or the ordering of parent nodes compared to their children.
大根堆 小根堆
Heap can be broadly classified in two types :
1. Min heap ：
A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes.
The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node.
Min Heap.png
2. Max heap:
A max heap is effectively the converse of a min heap; in this format, every parent node, including the root, is greater than or equal to the value of its children nodes.
The important property of a max heap is that the node with the largest, or maximum value will always be at the root node.
Max heap.png
Implementation
- Use array to store the data.
- Start storing from index 1, not 0.
- For any given node at position i:
Its Left Child is at [2i] if available.
Its right child is at [2i+1] if available.
Its Parent Node is at [i/2] if available. - Heap Majorly has 3 operations –
Insert Operation(Time complexity O(log n))
Delete Operation (Time complexity O(log n))
Extract-Min (OR Extract-Max) (Time complexity O(n))
Bubble-up Operation(往上冒泡)
Steps:
If inserted element is smaller than its parent node in case of Min-Heap OR greater than its parent node in case of Max-Heap, swap the element with its parent.
Keep repeating the above step, if node reaches its correct position, STOP.
Sink-Down Operation（往下沉落）
Steps:
If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
Keep repeating the above step, if node reaches its correct position, STOP.
