CSE 331 Lecture Notes - Lecture 6: Binary Heap, Priority Queue, Avl Tree
Priority Queue
• A priority queue is an ADT where the “most extreme” value is outputted first
• There’s a min priority queue:
o removeMin() returns element of smallest priority and removes it.
o peekMin() lets you find but not remove the min
• There’s also a max priority queue where the max elements/element with largest priority
is removed from the collection
• Overall 3 big behavior: removeMin, peekMin, and insert.
• We can use an AVL tree to implement this ADT since everything will be in log(n)
• But a better datastructure is a binary heap
Binary Heap
• A type of tree with new sets of invariants:
o Binary tree: Every node has at most two children
o Heap: Every node is smaller than its child
o Structure: Each level is “complete” meaning it has no “gaps”. Heaps are filled up
left to right
• With this, peekMin() is easy since we can just return the root node
• With removeMin(), replacing it with one of its children will cause a lot of gap when we
remove overallRoot.
• Rather than replacing it with a direct children, we can replace it with the most recently
inserted node. This will cause a broken heap since order isn’t maintained we will need to
swap.
• Percolating down: recursively swap parent with smallest child.
• To do insert, we will insert at the next empty node. If this breaks the heap, we will
percolate again, but start from the bottom and percolate up.
Implementing Heaps
• We actually implement heaps with arrays instead of trees
o The tree is only drawn to visually picture the heap
• This contiguous block of memory makes it easier to access
• To represent an array as a heap, start at the top and fill in from left to right
• The minimum node will be at the first index
• The last node is at index (size - 1)
