Pointer Dereferencing Levels
Understanding the four levels of pointer indirection in heap implementation
Level 1: ELEMENT
(*v)[i]->index
What it represents: One struct (index, key, pos)
Explanation: Direct access to struct fields
struct ELEMENT {
int index;
double key;
int pos;
};
Level 2: ELEMENT*
(*v)[i]
What it represents: Pointer to one struct
Explanation: Pointer to a single ELEMENT struct
(*v)[i] → ELEMENT
Level 3: ELEMENT**
*v
What it represents: Array of pointers to structs
Explanation: Array where each element points to an ELEMENT struct
*v[0] →
*v[1] →
*v[2] →
...
Level 4: ELEMENT***
v
What it represents: Pointer to the array itself
Explanation: Pointer to the array of pointers
v → Array of ELEMENT*
Key Implementation Relationships
Heap Access: pHeap->H[k] gives element index at heap position k
Key Access: (*v)[pHeap->H[i]]->key accesses key value at heap position i
Position Tracking: (*v)[element_index]->pos gives heap location of element
Critical Invariant: v[pHeap->H[k]]->pos == k must always hold
Min Heapify
Corrects a single violation of the min-heap property by moving an element down the tree.
Detailed Pseudocode
MinHeapify(heap, v, i):
# push the element at i down until the min-heap property holds
while i has at least one child:
j = index of the smaller child of i
if key(i) <= key(j):
break
swap i and j in the heap (also update v[*].pos)
i = j
Implementation Details
Pointer Dereferencing: pHeap->H[i] gives element index at heap position i
Key Access: (*v)[pHeap->H[i]]->key gets key value at heap position i
Position Tracking: (*v)[element_index]->pos gives heap location of element
Critical Invariant: v[pHeap->H[k]]->pos == k must always hold
Array (1-indexed):
Step 0 of 5
Starting with array [4, 2, 6, 8, 3, 7, 9] where position 1 violates min-heap property
Build Heap
Converts an arbitrary array into a min-heap by calling min-heapify from last non-leaf to root.
Detailed Pseudocode
BuildHeap(heap, v):
# turn an arbitrary array into a min-heap
set heap contents to elements 1..n and record their positions
for i from floor(n/2) down to 1:
MinHeapify(heap, v, i)
Implementation Details
Initialization: Set heap indices and position fields simultaneously
Last Non-leaf: floor(n/2) is the last node with children
Bottom-up: Process from last non-leaf to root ensures correctness
Time Complexity: O(n) - tighter than O(n log n) naive analysis
Array (1-indexed):
Step 0 of 4
Starting with array [9, 8, 7, 6, 5, 4, 3, 2, 1]. Last non-leaf node is at position 4.
Insert
Adds a new element to the heap and maintains the min-heap property by moving it up the tree.
Detailed Pseudocode
Insert(heap, v, element_index):
# add one element and restore heap order by bubbling up
append element_index at the end of the heap; set its position
i = current position of element_index
while i has a parent and key(parent(i)) > key(i):
swap i with parent(i) (also update positions)
i = parent(i)
Implementation Details
Bubble Up: Compare with parent and swap if necessary
Parent Access: Parent of position i is at position i/2
Position Updates: Both child and parent positions must be updated after swap
Termination: Stop when reaching root or heap property satisfied
Array (1-indexed):
Step 0 of 4
Inserting value 1.5 into heap [1, 2, 3, 4, 5, 6, 7]
Decrease Key
Decreases the value of a key at a given position and maintains min-heap property by moving it up.
Detailed Pseudocode
DecreaseKey(heap, v, element_index, new_key):
# lower an element's key, then bubble up like Insert
set key(element_index) = new_key
i = current position of element_index
while i has a parent and key(parent(i)) > key(i):
swap i with parent(i) (also update positions)
i = parent(i)
Implementation Details
Key Update: Directly modify the key value in the element
Position Lookup: Use (*v)[element_index]->pos to find heap position
Identical Logic: Same bubble-up process as Insert operation
Precondition: New key must be smaller than current key
Array (1-indexed):
Step 0 of 4
Decreasing key at position 4 from 8 to 0.5 in heap [1, 4, 3, 8, 5, 6, 7]
Extract Min
Removes and returns the minimum element (root) and restructures the heap to maintain min-heap property.
Detailed Pseudocode
ExtractMin(heap, v):
# remove and return the minimum (root) and restore the heap
if heap is empty:
return null
min_idx = root element's index
move last element to root and update its position
reduce heap size by one
MinHeapify(heap, v, 1)
return min_idx
Implementation Details
Root Replacement: Replace root with last element before decreasing size
Position Marking: Set extracted element's pos to 0 (not in heap)
Bubble Down: Use MinHeapify to restore heap property from root
Memory Management: Update all position fields before heapifying
Array (1-indexed):
Extracted Value:
-
Step 0 of 5
Extracting minimum from heap [1, 2, 3, 4, 5, 6, 7, 8, 9]