Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps - Coggle Diagram
Heaps
Properties
The height of a binary trees
of n nodes is floor(log2 n)
The root contains the largest key
Each sub-tree of a heap
is also a heap
Construction
Bottom-up
Starting with the last parental node
Check if parental
dominance is satisfied
Yes
Move to its parent
No
Switch the node's key K with
the largest key of its children
Move to the new position
of the key K
Construct a heap from a list of keys
Top-down
Insert a key in a pre-constructed heap
Insert a node with key K
after the last leaf
Compare K with
its parent's key
K >= parent's key
Switch K with its parent
The key of a node is greater than
the keys of their children
Parental dominance
Heapsort
Construct a heap for an array
Maximum key deletion n-1 times
Switch the root with the last leaf
Decrease the heap's size by 1
"Heapify" the remaing tree
Starting with the root
Complete binary tree