Heaps
Structure
Priority Queue
Item with Highest Priority
Find
Delete
Add
Shape Property
Essentially Complete
Parental Dominance or Heap Property
Father´s Key ≥ Son´s Key
Bottom-Up Heap Construction
Top-Down Heap Construction
Cworst(n) = 2(n − log2(n + 1))
Cinsert(n) ∈ O(log n)
Deletion
Root
Cdeletion(n) ∈ O(log n)
Heapsort
Structure
Array
Heap
Root Deletion n-1 times
Cworst,avg(n) ∈ Θ(n log n)