Heap

A heap refers to the heap tree-shaped data structure used in to implement a Priority Queue.

Resources: https://www.programiz.com/dsa/heap-data-structure

Why would you use Heap over BST?

The killer feature of heaps is the average time insertion into a binary heap is $O(1)$, for BST it is $O(\log (n))$.

I find it hard to see 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/

In 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 $O(\log n)$ levels, the insertion takes $O(\log n)$ time.

Questions

• Why implement a heap as an array than using nodes and pointers?
  • Nodes and their accompanying references use more space.
  • Nodes may not be stored contiguously in memory, so the time taken to access each node may be longer; array elements are stored contiguously - access time per heap item may be shorter.
  • It’s more straightforward using an array, since we have formulas and subroutines to handle fix-ups, fix-downs, inserts and deletes.
• Suppose heaps were implemented as trees (instead of arrays). Given two heaps $H_1$ and $H_2$ of the same height, a new heap can be created by building a new node with infinite priority and adding the root nodes of and as the left and right children, and then calling deleteMax.
  • False

Related

• Binary Heap
• Heap Sort
• Heapify