Definition
A heap is a specialized tree-based data structure that satisfies the heap property:
If A is a parent node of B, then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap.
Heaps can then be classified further as either “max heap” and “min heap”.
Details
We take max heap for example. The keys of parent nodes are always greater than or equal to the children node.
The heap is an implementation of priority queue. In fact, priority queues are often referred to as “heaps”, regardless of how they may be implemented.
Note that despite the similarity of the name “heap” to “stack” and “queue”, the latter two are abstract data types, while a heap is a specific data structure, and “priority queue” is the proper term for the abstract data type.
Insert
Add the element to the bottom level of the heap.
Compare the added element with its parent; if they are in the correct order, stop.
If not, swap the element with its parent and return to the previous step.
The number of operations required is dependent on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a time complexity of O(log n).
Delete
Replace the root of the heap with the last element on the last level.
Compare the new root with its children; if they are in the correct order, stop.
If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)
Time complexity
| Heap | Time |
|---|---|
| Find max | O(1) |
| Delete | O(lgn) |
| Insert | O(lgn) |
| Merge | O(n) |
How about building a heap?
It’s O(n).
Why? You may ask - “why not O(nlgn) like we do successive insert for n time”?
Read answers from stackoverflow.