Heap Data Structure

What is a Heap?

A heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for every node, the value of the node is greater than or equal to the values of its children. In a min heap, the value of the node is less than or equal to the values of its children. Heaps are used in algorithms like heap sort and in priority queues.

Real-World Analogy

Think of a heap as a pyramid of people where each person (node) has a higher rank (value) than the people they oversee (children). In a max heap, the highest-ranked person is at the top, and in a min heap, the lowest-ranked person is at the top.

Code Snippets

C++

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    std::cout << maxHeap.top() << std::endl; // Outputs 20
    return 0;
}

Java

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);
        System.out.println(maxHeap.peek()); // Outputs 20
    }
}

Python

import heapq

heap = []
heapq.heappush(heap, -10)
heapq.heappush(heap, -20)
heapq.heappush(heap, -5)
print(-heapq.heappop(heap)) # Outputs 20

C

#include <stdio.h>>
#include <stdlib.h>>

void maxHeapify(int *heap, int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < size && heap[left] > heap[largest])
        largest = left;
    if (right < size && heap[right] > heap[largest])
        largest = right;
    if (largest != i) {
        int temp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = temp;
        maxHeapify(heap, size, largest);
    }
}

int main() {
    int heap[] = {100, 50, 30, 20, 10, 5};
    maxHeapify(heap, 6, 0);
    printf("%d\n", heap[0]); // Outputs 100
    return 0;
}