Login
C Tutorials C++ Tutorials Java Tutorials Python Tutorials JavaScript Tutorials TypeScript Tutorials C# Tutorials Go Tutorials Rust Tutorials PHP Tutorials Kotlin Tutorials Swift Tutorials
HTML Tutorials CSS Tutorials Frontend Development Backend Development React Tutorials Next.js Tutorials Node.js Tutorials Django Tutorials Mobile App Development
Beginner Tutorials Advanced Guides Coding Roadmaps Interview Preparation DSA Tutorials Projects & Examples Cheat Sheets
About Us Contact Privacy Policy Terms & Conditions Disclaimer Sitemap

Heaps & Priority Queues: Structure, Operations, and Mechanics

A Priority Queue is an Abstract Data Type (ADT) where each element has an assigned priority. In a standard First-In-First-Out (FIFO) queue, elements are dequeued in the exact order they arrive; in a priority queue, the element with the highest (or lowest) priority is always served first.

While priority queues can theoretically be implemented using arrays or linked lists, the Binary Heap is the standard underlying data structure. It delivers an optimal trade-off: O(log N) insertion, O(log N) extraction, and O(1) peek time.

The Core Properties of a Binary Heap

A Binary Heap is a specialized tree structure governed by two invariant rules:

  • Shape Property (Complete Binary Tree): Every level of the tree is completely filled, with the possible exception of the bottom level, which must be filled strictly from left to right.
  • Heap-Order Property (Max-Heap vs. Min-Heap): In a Max-Heap, every parent node is greater than or equal to its children (the root contains the maximum). In a Min-Heap, every parent node is less than or equal to its children (the root contains the minimum).

Efficient Array-Based Representation

Because a binary heap is guaranteed to be a complete binary tree, it requires no pointer nodes or references. It can be stored compactly in a contiguous zero-indexed array where tree relationships are computed through arithmetic indices:

  • Root Element: Always located at index 0.
  • Left Child of node i: Located at index (2 * i) + 1.
  • Right Child of node i: Located at index (2 * i) + 2.
  • Parent of node i: Located at index (i - 1) / 2 (integer floor division).

Core Heap Operations and Time Complexities

1. Insertion / Push - Sift-Up (Percolate-Up)

To insert an element: append it to the end of the array (preserving the shape property), then repeatedly compare it with its parent. If the heap invariant is violated, swap it upward until it reaches its valid level or becomes the root. Time Complexity: O(log N).

2. Extract Minimum/Maximum - Sift-Down (Percolate-Down)

To remove the top element: remove the root, move the last element in the array to the root position, and sift it downward by repeatedly swapping with the smaller child (for Min-Heap) or larger child (for Max-Heap) until order is restored. Time Complexity: O(log N).

3. Peek / Top

Directly inspect array index 0. Time Complexity: O(1).

4. Build-Heap (Bottom-Up Heapify)

Converting an arbitrary unsorted array into a valid heap can be done by running sift-down on all non-leaf nodes starting from index (N / 2 - 1) down to index 0. This achieves an overall time complexity of O(N), significantly faster than N successive insertions.

Real-World Applications & Algorithms

  1. Dijkstra's Shortest Path & Prim's MST: Min-Priority Queues continuously retrieve the nearest unvisited node or lowest-weight edge.
  2. Operating System Task Schedulers: Completely Fair Schedulers (CFS) and real-time thread dispatchers prioritize time-critical execution threads.
  3. Top-K Elements and Running Medians: Two-heap patterns (Min-Heap + Max-Heap) track dynamic medians in continuous data streams.
  4. Heap Sort: An in-place O(N log N) sorting algorithm that avoids worst-case O(N^2) regression without requiring extra auxiliary memory.