Learn Heap Introduction — Free DSA Tutorial

What is a Heap?

A heap is a complete binary tree — meaning every level is fully filled except possibly the last, which fills from left to right — and that completeness is exactly what makes it possible to store a heap efficiently in a plain array instead of using node objects with pointers.

Example: What is a Heap?

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    cout << "Complete binary tree stored as array: every level full except last, filled left to right" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] heap = {50, 30, 40, 10, 20};
        System.out.println("Complete binary tree stored as array: every level full except last, filled left to right");
    }
}

heap = [50, 30, 40, 10, 20]
print("Complete binary tree stored as array: every level full except last, filled left to right")

#include <stdio.h>
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    printf("Complete binary tree stored as array: every level full except last, filled left to right\n");
    return 0;
}

Complete Binary Tree

Because a heap fills each level left to right with no gaps, there's a direct, predictable formula mapping between array indices and the tree's parent/child relationships, so the tree structure can be reconstructed purely from array positions.

Example: Complete Binary Tree

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    int i = 1;
    cout << "Parent of index " << i << " is index " << (i-1)/2 << " (predictable via formula, no pointers needed)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int i = 1;
        System.out.println("Parent of index " + i + " is index " + (i-1)/2 + " (predictable via formula, no pointers needed)");
    }
}

i = 1
print("Parent of index", i, "is index", (i - 1) // 2, "(predictable via formula, no pointers needed)")

#include <stdio.h>
int main() {
    int i = 1;
    printf("Parent of index %d is index %d (predictable via formula, no pointers needed)\n", i, (i-1)/2);
    return 0;
}

Parent and Child

For a node stored at array index i, its left child sits at index 2i+1 and its right child at index 2i+2 — these formulas let heap operations navigate the tree using simple arithmetic instead of following pointers.

Example: Parent and Child

#include <iostream>
using namespace std;
int main() {
    int i = 1;
    cout << "left child=" << 2*i+1 << " right child=" << 2*i+2 << " for parent index " << i << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int i = 1;
        System.out.println("left child=" + (2*i+1) + " right child=" + (2*i+2) + " for parent index " + i);
    }
}

i = 1
print("left child=", 2*i+1, "right child=", 2*i+2, "for parent index", i)

#include <stdio.h>
int main() {
    int i = 1;
    printf("left child=%d right child=%d for parent index %d\n", 2*i+1, 2*i+2, i);
    return 0;
}

Heap Property

A max heap enforces that every parent is greater than or equal to its children, which guarantees the largest value in the whole structure always sits at the root; a min heap enforces the opposite, keeping the smallest value at the root.

Example: Heap Property

#include <iostream>
using namespace std;
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    cout << "Max heap: every parent >= children, so heap[0]=" << heap[0] << " is the largest value overall" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] heap = {50, 30, 40, 10, 20};
        System.out.println("Max heap: every parent >= children, so heap[0]=" + heap[0] + " is the largest value overall");
    }
}

heap = [50, 30, 40, 10, 20]
print("Max heap: every parent >= children, so heap[0]=", heap[0], "is the largest value overall")

#include <stdio.h>
int main() {
    int heap[] = {50, 30, 40, 10, 20};
    printf("Max heap: every parent >= children, so heap[0]=%d is the largest value overall\n", heap[0]);
    return 0;
}

Heap Practice

Heaps are the standard structure behind priority queues (where you always need fast access to the highest or lowest priority item) and are also the basis for heap sort, since repeatedly removing the root of a heap yields elements in sorted order.

Example: Heap Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Heaps back priority queues: always fast access to the highest/lowest priority item" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Heaps back priority queues: always fast access to the highest/lowest priority item");
    }
}

print("Heaps back priority queues: always fast access to the highest/lowest priority item")

#include <stdio.h>
int main() {
    printf("Heaps back priority queues: always fast access to the highest/lowest priority item\n");
    return 0;
}

Heap Introduction

What is a Heap?

Complete Binary Tree

Parent and Child

Heap Property

Heap Practice

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code