Please enable JavaScript.
Coggle requires JavaScript to display documents.
(M10) CHAPTER 6 (6.4) - Coggle Diagram
(M10) CHAPTER 6 (6.4)
Heap
Partially ordered data structure that is suitable for implementing priority queues.
Binary tree with keys with the following conditions:
Shape property
Complete binary tree
Heap property
Each key is greater than or equal to its children
Values are ordered top down
Properties
Complete binary tree with n nodes, its height is floor(log2 n)
The root is the largest element
The subtree of a heap is also a heap
Heap can be a array recording in the top-down and left-right fashion
Position 'i' has your children in position 2i and 2i +1
Heapsort
Two stage algorithm
Heap constrution
Maximum deletions
Time efficiency: Θ(n log n)
Quicksort is better than heapsort while heapsort can compete with mergesort
Applied by deletions operations