# 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?

I have trouble seeing the use case of heaps.

          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.