Heap
A heap refers to the heap tree-shaped data structured used in to implement a Priority Queue.
Do confused this with the Heap (Memory). There is no connection between them.
Resources
Binary Heap
A Binary Heap is another way of implementing a Priority Queue. A binary heap is a heap, i.e, a tree which obeys the heap property: the root of any tree is greater than or equal to (or smaller than or equal to) all its children.
Heap Invariant: for ALL subtrees, root > left child, right child
Heap vs Tree
Heap vs. Self-Balancing Binary Search Tree?
- Because Heap implements the Priority Queue, whereas Self-Balancing Binary Search Tree implements the Ordered Map in C++.
I have trouble seeing the use case of heaps.
- https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bs
- https://www.baeldung.com/cs/heap-vs-binary-search-tree
- https://www.geeksforgeeks.org/difference-between-binary-search-tree-and-binary-heap/
Type BST (*) Heap
Insert average log(n) 1
Insert worst log(n) log(n) or n (***)
Find any worst log(n) n
Find max worst 1 (**) 1
Create worst n log(n) n
Delete worst log(n) log(n)
Why would you use Heap over BST?
The killer feature of heaps is that average time insertion into a binary heap is , for BST is .
Heaps are great to get the minimum or the maximum value in . However, if you want to search for a particular key, you are better off using a BST.
CS240
When inserting a heap, you always need to put it in the left-most. Then, you do a swap operation. Since there are at most levels, the insertion takes time.
We take the child with the larger key
Storing Heaps in Arrays
Heaps should not be stored as binary trees! Let H be a heap of n items and let A be an array of size n. Store root in and continue with elements level-by-level from top to bottom, in each level left-to-right
This is exactly how we encode it in a Segment Tree! (except we use 1-index?)
It is easy to navigate the heap using this array representation:
- the root node is at index 0 (We use “node” and “index” interchangeably in this implementation.)
- the last node is (where n is the size)
- the left child of node i (if it exists) is node
- the right child of node i (if it exists) is node
- the parent of node i (if it exists) is node
- these nodes exist if the index falls in the range
In practice, use 1-indexing
It is more convenient to use 1-indexing. See Segment Tree for how this is implemented.
The Priority Queue uses the heap. In C++, the underlying implementation is a C++ Vector.