Heap Flashcards
Use cases for a Max-Heap.
Priority Queue, e.g. OS task-scheduling, a OS update should be given a lower-priority than any other user started tasks and so shouldn’t run until they complete.
A Priority Queue is an example use of a Max-Heap, what is a real-world analogy/example of a Max-Heap?
A hospital A+E ward. Triage will give patients a priority value based on their injuries/condition and those with the highest priority will be attended to first.
Heap definition…
A special tree in which each level contains Node’s with values more extreme (either greater than or less than), the Nodes on the level above it.
What does a Min-Heap do?
It ensures that the node with the LOWEST value is always at the top of the tree.
What does a Max-Heap do?
It ensures that the node with the HIGHEST values is always at the top of the tree.
Min-Heap’s two defining properties?
- The value at the Root Node must be the MINIMUM amongst all of its children.
- This fact must be the same recursively for all parent Nodes contained within the Heap.
Min-Heap’s two defining properties?
- The value at the Root Node must be the MAXIMUM amongst all of its children.
- This fact must be the same recursively for all parent Nodes contained within the Heap.
How do we ADD an element to a Heap?
- Add the node to the most Bottom-Left position available. If a hierarchy-level has free space then it goes to the left-most free spot on that level. If not, then it will go down to a new level from the left-most leaf.
- Recursively go up the tree and swap Nodes if necessary. Max-Heap: If larger then parent, then swap. Min-Heap: If smaller than parent then swap.
How do we DELETE an element from a Heap? (3)
- Remove the root node from our heap. You will likely return this value to the caller.
- Replace it with the Node furthest to the bottom-right.
- “Heapify” the Heap bu comparing parent Node’s to their children and swapping if necessary.
What is “Heapifying”?
It fixes the heap to ensure the max/min value is always at the root. You compare the Root Node to its children and swap if necessary. Repeat through all parent nodes in the tree.
What sorting algorithm uses a Heap?
The Heap Sort.
How does a Heap Sort work?
It takes all the values to be sorted and builds a Heap Tree. It then takes the Root Node’s value and adds it to its sorted list. It then “heapify’s” the tree to ensure the Highest/Lowest value is at the Root Node and repeats until the Tree is empty.
What is the Big(O) of ACCESS a heap?
O(1). Simply getting the Root Node.
What is the Big(O) of RE-BALANCING “Heapifying” a heap?
O(log n). Why?
