Binary Heap

Definition and Structure

Binary Heap Concept

Binary heap: complete binary tree, satisfies heap property, used for efficient priority management. Nodes arranged level-wise, left to right, no gaps.

Structure Characteristics

Complete binary tree: all levels full except possibly last, filled left to right. Balanced height: ⌊log₂ n⌋ for n nodes.

Tree vs Array Representation

Logical tree structure mapped to array form: parent and child indices calculated via formulas; eliminates explicit pointers.

Heap Property

Definition

Property enforcing order: parent node key ≥ (max-heap) or ≤ (min-heap) children keys. Ensures root node as extreme element.

Implications

Partial ordering: entire tree not fully sorted, only local ordering between parent and children. Enables efficient access to extremum.

Maintenance

Operations preserve heap property via shifting elements up or down (bubble-up, bubble-down) after insertions or deletions.

Types of Binary Heaps

Min-Heap

Parent key ≤ children keys. Root holds minimum element. Used in algorithms requiring quick minimum retrieval.

Max-Heap

Parent key ≥ children keys. Root holds maximum element. Suitable when maximum element access is priority.

Variants and Extensions

Fibonacci heaps, d-ary heaps, skew heaps offer alternative trade-offs. Binary heap often baseline for priority queues.

Array Representation

Indexing Scheme

Root at index 0 (or 1). For node at index i: left child at 2i + 1, right child at 2i + 2, parent at ⌊(i-1)/2⌋.

Advantages

Space efficient: no pointers. Cache-friendly due to contiguous memory layout. Simplifies traversal and computations.

Limitations

Fixed size arrays require resizing for dynamic heaps. Sparse or unbalanced trees inefficiently represented.

Core Operations

Insertion

Insert element at end, "bubble-up" by swapping with parent until heap property restored.

Extract Root

Remove root (min or max), replace with last element, "bubble-down" to restore heap property.

Peek

Access root element without removal, constant time O(1).

Increase/Decrease Key

Adjust node key, bubble-up or bubble-down accordingly to maintain heap property.

Delete

Replace target with last element, adjust heap via bubble operations.

Heapify Process

Bottom-Up Heapify

Build heap from arbitrary array by applying bubble-down from last non-leaf to root.

Top-Down Heapify

Insert elements one by one, bubbling up each time, less efficient than bottom-up.

Time Complexity

Bottom-up heapify: O(n). Top-down insertion heapify: O(n log n).

function heapify(array): for i = lastNonLeafIndex down to 0: bubbleDown(array, i)

Time and Space Complexity

Time Complexity of Operations

Space Complexity

O(n) for storing n elements. Array representation requires contiguous memory.

Binary Heap as Priority Queue

Definition

Priority queue: abstract data type allowing element insertion and retrieval of highest/lowest priority element efficiently.

Implementation

Binary heap: underlying data structure for priority queues due to efficient insert and extract-min/max operations.

Performance Impact

Supports real-time scheduling, event simulation, Dijkstra’s shortest path, and Huffman coding.

Applications

Sorting: Heapsort

Heapsort: build heap from array, repeatedly extract root to produce sorted list. Time: O(n log n), space: O(1).

Graph Algorithms

Dijkstra’s algorithm: priority queue manages vertices by tentative distances. Prim’s MST: selects edges with minimum weight efficiently.

Real-Time Systems

Task scheduling and bandwidth management leverage priority queues for efficient priority handling.

Memory Management

Garbage collection and resource allocation can utilize heaps for priority-based decisions.

Implementation Details

Data Structures Used

Array for storage. Integer indices for parent/child navigation. Simple swap operations for restructuring.

Bubble-Up Algorithm

function bubbleUp(array, index): while index > 0 and array[parent(index)] > array[index]: swap(array[parent(index)], array[index]) index = parent(index)

Bubble-Down Algorithm

function bubbleDown(array, index): smallest = index left = leftChild(index) right = rightChild(index) if left < size and array[left] < array[smallest]: smallest = left if right < size and array[right] < array[smallest]: smallest = right if smallest != index: swap(array[index], array[smallest]) bubbleDown(array, smallest)

Edge Cases

Empty heap extraction: error or null. Single element insertion: trivial bubble-up. Duplicate keys: maintain insertion order or stable heap.

Advantages and Disadvantages

Advantages

Simple implementation. Efficient memory usage. Fast insertion and extraction. Cache-friendly layout.

Disadvantages

Limited to partial order. Not efficient for decrease-key operations compared to Fibonacci heaps. Poor worst-case for arbitrary element deletion.

Trade-offs

Binary heap balances simplicity and speed. Advanced heaps optimize for specific operations at cost of complexity.

Comparisons with Other Heaps

Binary vs Fibonacci Heap

Binary heap: O(log n) insert/extract. Fibonacci heap: O(1) amortized insert, O(log n) extract-min. Fibonacci better for decrease-key intensive tasks.

Binary vs d-ary Heap

d-ary heap: higher branching factor reduces tree height, faster insertions, slower extract-min. Binary heap simpler to implement.

Binary vs Pairing Heap

Pairing heaps offer simpler implementation than Fibonacci with comparable amortized bounds, but binary heaps remain standard in many applications.

References

• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, 3rd ed., MIT Press, 2009, pp. 155-176.
• Williams, J.W.J., Algorithm 232: Heapsort, Communications of the ACM, Vol. 7, No. 6, 1964, pp. 347-348.
• Fredman, M.L., Tarjan, R.E., Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, Vol. 34, No. 3, 1987, pp. 596-615.
• Knuth, D.E., The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, pp. 165-192.
• Tarjan, R.E., Data Structures and Network Algorithms, SIAM, 1983, pp. 95-110.