10. Heap

Introduction

A heap is a specialized tree‑based data structure that satisfies the heap property: in a min‑heap every parent node is less than or equal to its children, while in a max‑heap every parent node is greater than or equal to its children. Heaps are commonly used to implement priority queues because the highest (or lowest) priority element can be accessed in constant time and updated efficiently.

Array‑Based Representation

Heaps are stored implicitly in an array, which allows efficient use of memory and simple index calculations. For a node at index i (0‑based):

• Left child index: 2*i + 1
• Right child index: 2*i + 2
• Parent index: Math.floor((i‑1)/2)

Example: the array [2,5,3,9,6,8] represents the tree

      2
    /   \
   5     3
  / \   /
 9   6 8

Here the root is at index 0, its left child at index 1 (value 5), right child at index 2 (value 3), and so on.

Min‑Heap

In a min‑heap the smallest element resides at the root. The heap property is:

parent ≤ left child and parent ≤ right child for every node.

Example array [2,5,3,9,6,8] already satisfies the min‑heap property, as shown above.

Max‑Heap

Conversely, a max‑heap places the largest element at the root. The heap property becomes:

parent ≥ left child and parent ≥ right child.

The array [9,6,8,2,5,3] yields the following max‑heap:

      9
    /   \
   6     8
  / \   /
 2   5 3

The root (index 0) holds the maximum value 9.

Heap Operations

All heap operations run in O(log n) time except peek, which is O(1). The two key procedures are heapify‑up (used after insertion) and heapify‑down (used after removal).

Insert (push)

1. Place the new element at the first free position (end of the array).
2. While the element violates the heap property with its parent, swap it with the parent.
3. Continue moving upward until the property is restored.

Pseudo‑code (min‑heap):

function insert(value): heap.append(value) i = heap.length - 1 while i > 0 and heap[parent(i)] > heap[i]: swap(heap[i], heap[parent(i)]) i = parent(i)

The loop executes at most the height of the tree → O(log n).

Extract‑Min / Extract‑Max (pop)

1. If the heap is empty, raise an error.
2. Save the root value (the element to return).
3. Replace the root with the last element in the array and reduce the heap size by one.
4. Perform heapify‑down on the new root:
• Compare the node with its children.
• For a min‑heap, swap with the smaller child; for a max‑heap, swap with the larger child.
• Repeat until the heap property holds.

Pseudo‑code (extract‑min):

function extractMin(): if heap.isEmpty(): throw Error min = heap[0] heap[0] = heap[heap.length-1] heap.pop() heapifyDown(0) return min function heapifyDown(i): left = 2*i + 1 right = 2*i + 2 smallest = i if left < heap.length and heap[left] < heap[smallest]: smallest = left if right < heap.length and heap[right] < heap[smallest]: smallest = right if smallest != i: swap(heap[i], heap[smallest]) heapifyDown(smallest)

Again, the depth of the tree bounds the runtime to O(log n).

Peek

Return the root element without modifying the heap:

function peek(): return heap[0] // O(1)

Heapify (Build Heap from Arbitrary Array)

To convert an unordered array into a heap, start from the last internal node and apply heapify‑down moving towards the root.

The last internal node index is ⌊n/2⌋‑1 (0‑based).

function buildHeap(array): heap = array.copy() start = Math.floor(heap.length/2) - 1 for i from start down to 0: heapifyDown(i) return heap

Although each heapifyDown call may cost O(log n), the total work sums to O(n) because most nodes are near the leaves and have small height.

Heap Sort

Heap sort uses a max‑heap to sort an array in ascending order in‑place.

1. Build a max‑heap from the input array (O(n)).
2. Repeat n times:
   • Swap the root (maximum) with the last element of the current heap.
   • Reduce the heap size by one (the swapped element is now in its final sorted position).
   • Call heapify‑down on the new root to restore the max‑heap property.
3. After the i-th iteration, the suffix [n‑i … n‑1] contains the i largest elements in sorted order.

Overall time complexity: O(n log n). Space complexity: O(1) (in‑place). Heap sort is not stable.

Example Walk‑through

Sort the array [4,10,3,5,1]:

Step	Array (heap portion)	Action
Build max‑heap	[10,5,3,4,1]	–
Swap 10↔1	[1,5,3,4,10]	Heapify root → [5,4,3,1,10]
Swap 5↔1	[1,4,3,5,10]	Heapify root → [4,1,3,5,10]
Swap 4↔1	[1,3,4,5,10]	Heapify root → [3,1,4,5,10]
Swap 3↔1	[1,3,4,5,10]	Heapify root → [3,1,4,5,10] (no change)
Done	[1,3,4,5,10]	Sorted array

Applications

Heaps underlie priority queues, which appear in many real‑world systems.

1.2.1 Task Scheduling

Operating systems and job schedulers often assign a priority number to each task. A max‑heap (or min‑heap depending on priority convention) lets the scheduler extract the highest‑priority task in O(log n) time and insert new tasks with the same complexity.

Example: priorities {5,2,9,1} → max‑heap yields extraction order 9,5,2,1.

1.2.2 Emergency Queue

In triage or emergency departments, patients are assigned a severity score (higher = more urgent). A max‑heap enables:

• Insertion of a new patient in O(log n).
• Removal of the most urgent patient (the root) in O(log n).

Thus the system always attends to the patient needing immediate care.

1.2.3 Event Management (Simulation)

Discrete‑event simulations keep a queue of future events ordered by their timestamps. A min‑heap of event times guarantees that the next event to process is always the earliest:

• Extract the minimum timestamp (O(log n)).
• Process the event, possibly generating new events.
• Insert each new event into the heap (O(log n)).

This yields overall O(log n) per event, ensuring chronological processing without sorting the entire list repeatedly.

Summary

Heaps provide an efficient way to maintain a collection where the extremal element (minimum or maximum) must be accessed quickly. Their array‑based layout simplifies implementation, while the logarithmic cost of insertions and deletions makes them suitable for dynamic scenarios such as scheduling, priority‑based queues, and simulations. Understanding heap sort also illustrates how the same structure can be leveraged for in‑place sorting with guaranteed O(n log n) performance.