heaps = an ADT-like-thingy that allows us to implement stuff like priority queues

heaps can be conceptualised as dense tree structures

• tree maintains a general order with higher elements up the top
• new items are added initially at lower-most, then right-most leaf, which then ‘drift up’ to appropriate level in tree
• items are always deleted by removing the root
• since heaps are dense trees, depth = floor($\log_2N$) + 1

heaps are often implemented as arrays (given that we know the max size)

simple index calculations allow traversal through tree:

for an item at index $i$,

• left child of item is located at $2i$
• right child of item is located at $2i+1$
• parent of item is located at floor($i/2$)

generally don’t store anything at index 0 so that the above index calculations work easily

typedef struct HeapRep {
	Item *items; // array of items
	int nitems; // number of items in array
	int nslots; // number of slots in array (basically a max-size)
} HeapRep;

typedef HeapRep *Heap;

• heap create

• heap insertion

• heap delete