Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps - Coggle Diagram
Heaps
Binary tree with keys assigned to its nodes, with one key per node.
-
-
Specially suitable for implementing priority queues, having efficient implementation of its operations.
Properties
There is exactly one essentially complete binary tree with n nodes, with height equal to log2 n.
-
-
A heap can be represented in an array, with a top-down, left-to-right distribution.
The first ⌊n/2⌋ positions are occupied by parents, whilst the last ⌈n/2⌉ positions are occupied by the leaves.
The children of a key in the array's parental position will be in positions 2i and 2i+1. Consequently, the parent of a key in position i will be in position ⌊i/2⌋.
Bottom-up construction: checks if the parental dominance applies to the binary tree, starting from the leaves and going up.
A heap of size n can be constructed in O(n) (no more than 2n, to be precise).
-
Deletion: Swap the desired key to be removed with the last key and heapify the heap once again. Is in O(log n).
Heapsort
- Construct a heap for a given array
- Apply the root-deletion operation n - 1 times to the remaining heap.
This way, since the root is always the largest element, the key to be deleted will also be the greatest value from the heap.
-