Algorithm


A heap is a specialized tree-based data structure that satisfies the heap property. The heap property depends on the type of heap, but in a binary heap, which is a common type of heap, it can be either of the following:

  1. Min-Heap Property: In a min-heap, for every node i other than the root, the value of i is greater than or equal to the value of its parent.

  2. Max-Heap Property: In a max-heap, for every node i other than the root, the value of i is less than or equal to the value of its parent.

Heap data structures are commonly implemented using arrays. In a binary heap, the parent and children relationships can be easily represented using array indices. For a node at index i:

  • Its left child is at index 2*i + 1.
  • Its right child is at index 2*i + 2.
  • Its parent is at index (i-1)/2 (integer division).

The key operations performed on a heap include:

  1. Insertion: Adding a new element to the heap. The element is initially placed at the bottom of the heap and then "bubbled up" to its correct position to maintain the heap property.

  2. Deletion: Removing the root element from the heap. After removal, the last element in the heap is moved to the root position and then "bubbled down" to its correct position to maintain the heap property.

  3. Peek (or Find-Min/Max): Returning the root element without removing it.

Heap data structures are commonly used in various algorithms and applications, including heap sort, priority queues, and implementing certain graph algorithms like Dijkstra's algorithm.

 

Code Examples

#1 Heap Data Structure implement in python

Code - Python Programming

import heapq

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        heapq.heappush(self.heap, value)

    def pop(self):
        if self.is_empty():
            raise IndexError("Heap is empty")
        return heapq.heappop(self.heap)

    def peek(self):
        if self.is_empty():
            raise IndexError("Heap is empty")
        return self.heap[0]

    def is_empty(self):
        return len(self.heap) == 0

# Example usage:
min_heap = MinHeap()
min_heap.push(3)
min_heap.push(1)
min_heap.push(4)
min_heap.push(2)

print("Min heap elements:", min_heap.heap)

while not min_heap.is_empty():
    print("Pop:", min_heap.pop())
Copy The Code & Try With Live Editor

#2 Heap Data Structure implement in Java

Code - Java Programming

import java.util.Arrays;

public class MinHeap {
    private int capacity;
    private int size;
    private int[] heap;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full. Cannot insert more elements.");
            return;
        }

        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] > heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    public int extractMin() {
        if (size  < = 0) {
            System.out.println("Heap is empty. Cannot extract minimum element.");
            return -1; // or throw an exception
        }

        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);

        return min;
    }

    private void heapifyDown(int index) {
        int left = leftChild(index);
        int right = rightChild(index);
        int smallest = index;

        if (left  <  size && heap[left] < heap[smallest]) {
            smallest = left;
        }

        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (index != smallest) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    public void printHeap() {
        System.out.println(Arrays.toString(heap));
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);

        minHeap.insert(3);
        minHeap.insert(2);
        minHeap.insert(1);
        minHeap.insert(5);
        minHeap.insert(4);

        System.out.print("Min Heap: ");
        minHeap.printHeap();

        System.out.println("Min Element: " + minHeap.extractMin());

        System.out.print("Heap after extracting minimum element: ");
        minHeap.printHeap();
    }
}
Copy The Code & Try With Live Editor

#3 Heap Data Structure implement in C

Code - C Programming

#include <stdio.h>

#define MAX_HEAP_SIZE 100

// Function to swap two elements in the array
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree with the root at given index
void minHeapify(int heap[], int size, int index) {
    int smallest = index;  // Initialize the root as the smallest
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;

    // If the left child is smaller than the root
    if (leftChild  <  size && heap[leftChild] < heap[smallest]) {
        smallest = leftChild;
    }

    // If the right child is smaller than the root
    if (rightChild < size && heap[rightChild] < heap[smallest]) {
        smallest = rightChild;
    }

    // If the smallest is not the root, swap and recursively heapify the affected subtree
    if (smallest != index) {
        swap(&heap[index], &heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

// Function to insert a new element into the heap
void insertHeap(int heap[], int *size, int element) {
    if (*size >= MAX_HEAP_SIZE) {
        printf("Heap overflow: Cannot insert more elements.\n");
        return;
    }

    // Insert the new element at the end
    heap[*size] = element;
    (*size)++;

    // Heapify the tree from the bottom up
    int i = *size - 1;
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Function to extract the minimum element from the heap
int extractMin(int heap[], int *size) {
    if (*size  < = 0) {
        printf("Heap underflow: Cannot extract from an empty heap.\n");
        return -1; // Assuming -1 as a sentinel value for an error
    }

    // The root of the heap contains the minimum element
    int minElement = heap[0];

    // Replace the root with the last element and heapify the tree
    heap[0] = heap[*size - 1];
    (*size)--;

    minHeapify(heap, *size, 0);

    return minElement;
}

// Function to print the elements of the heap
void printHeap(int heap[], int size) {
    printf("Heap elements: ");
    for (int i = 0; i  <  size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main() {
    int heap[MAX_HEAP_SIZE];
    int heapSize = 0;

    // Example usage
    insertHeap(heap, &heapSize, 3);
    insertHeap(heap, &heapSize, 2);
    insertHeap(heap, &heapSize, 1);
    insertHeap(heap, &heapSize, 4);

    printHeap(heap, heapSize);

    printf("Min element: %d\n", extractMin(heap, &heapSize));

    printHeap(heap, heapSize);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Heap Data Structure implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>

class MaxHeap {
private:
    std::vector<int> heap;

    void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        while (index > 0 && heap[index] > heap[parent]) {
            std::swap(heap[index], heap[parent]);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild  <  heap.size() && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }

        if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) {
            std::cerr << "Heap is empty." << std::endl;
            return -1; // or some sentinel value
        }

        int maxValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);

        return maxValue;
    }

    void printHeap() {
        std::cout << "Heap: ";
        for (int value : heap) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    MaxHeap maxHeap;

    maxHeap.insert(10);
    maxHeap.insert(7);
    maxHeap.insert(15);
    maxHeap.insert(5);
    maxHeap.insert(20);

    maxHeap.printHeap();

    int max = maxHeap.extractMax();
    std::cout << "Extracted Max Value: " << max << std::endl;

    maxHeap.printHeap();

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Heap Data Structure-DevsEnv