Prerequisite
A strong understanding of trees is a must in order to understand the working of heap.
Almost Complete Binary Tree
A binary tree (binary means every node can have at most two childrens) is said to be an almost complete binary tree when:
- All levels except the last are completely filled: Every level of the tree (from the root to the level just before the last) must have the maximum number of nodes possible for that level.
- The last level is filled from left to right: The nodes at the last level are arranged as far to the left as possible, with no gaps between them.
This is importance because the heap data structure is internally maintained as an
Almost Complete Binary Tree.
Heap
A heap is a special tree-based data structure that satisfies the heap property. It is commonly used to efficiently solve problems involving priority and to implement algorithms like sorting and finding the smallest or largest elements.
Heap Property
The heap property defines the relationship between a parent node and its child nodes in a heap. This property ensures that the structure of the heap remains consistent for efficient operations. The exact nature of this relationship depends on the type of heap.
There are two types of heaps:
- Min-Heap: The value of each parent node must be less than or equal to the values of its child nodes. This ensures that the smallest element is always at the root of the heap.
- Max-Heap: The value of each parent node must be greater than or equal to the values of its child nodes. This ensures that the largest element is always at the root of the heap.
Key Points about the Heap Property:
1. Local Relationship:
The heap property only ensures that a parent node maintains its relationship with its immediate children. It does not impose any order between sibling nodes or across levels.
2. Preservation During Operations:
When elements are inserted or removed, the heap property might temporarily be violated. A process called heapification restores the property by adjusting the positions of elements.
/Image_1-j8Jv0sTm)
Internal Representation of Heap
The internal implementation of a heap utilizes the array representation of a heap rather than the tree structure discussed earlier. This highlights the importance of understanding how an almost complete binary tree is represented using an array.
Indexing Technique to Represent the Tree
- Root Node: The root of the tree is stored at index 0 (following the 0-based indexing).
- Parent-Child Relationships: For a node at index i:
- Left Child: The left child is located at index
2*i + 1.
- Right Child: The right child is located at index
2*i + 2.
- Parent: The parent is located at index
⌈i/2⌉ - 1
/Image_2-zS7fnW8i)
Example Conversion:
/Image_3-CF1aVk9Y)
Indices of Leaf Nodes and Non-leaf Nodes
Leaf Nodes
Leaf nodes are the nodes without any children, and they always appear in the last level (or partially in the second-last level if the last level is incomplete).
In an array representation of a binary tree with N elements
- Range of Leaf Node Indices: Leaf Nodes start from the index
⌊N/2⌋ to n-1 (both inclusive).
Non-leaf Nodes
Non-leaf nodes are the nodes that have at least one child.
In an array representation of a binary tree with N elements
- Range of Non-leaf Node Indices: Non-leaf Nodes start from the index
0 to ⌊N/2⌋ - 1 (both inclusive).
Example
/Image_4-zqbd5I9F)