Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap - Coggle Diagram
Heap
Priority Queue
Stores items in a priority-manner
Largest-to-smallest or vice-versa
"Heap property"
Max-heap: the key in each node is greather than or equal to is children
Min-heap: the key in each node less than or equal to it's children key
Heap implementation
Binary tree
Straightfoward
More intuitive
Much less efficient
Array
Parent node are stored in the first n/2 positions
Child nodes are stored in the last n/2 positions
A node's children are in positions 2i and 2i + 1
A Node's parent is at position i/2
More efficient
Bottom-up construction
Initializes the complete tree as given then "heapifies it"
Heapification
Exchange parent with child if parental dominance doesn't hold
Process continues until parental dominance is satified for that key
Do the same for the node's predecessor
Stops when dominance holds for root
Top-down construction
Start with empty heap
Keep inserting key's in the heap preserving dominance
Stores largest element at the root
The tree is always complete