In data structures, a heap is a specialized binary tree-based data structure that satisfies the heap property. The heap property ensures that the key (value) of each node in the tree is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the keys of its children.
There are two common forms of heaps:
1. Max Heap: In a max heap, the parent nodes have keys greater than or equal to the keys of their children, and the maximum key is at the root of the heap.
2. Min Heap: In a min heap, the parent nodes have keys less than or equal to the keys of their children, and the minimum key is at the root of the heap.
Example of a max heap:
```
10
/ \
7 8
/ \ /
5 6 4
```
Example of a min heap:
```
3
/ \
5 6
/ \ /
9 8 11
```
Applications and Uses of Heaps:
1. Priority Queues: Heaps are commonly used to implement priority queues, where elements with higher priority are dequeued before elements with lower priority.
2. Heap Sort: Heaps can be used to efficiently implement heap sort, which is an efficient comparison-based sorting algorithm.
3. Dijkstra's Algorithm: Heaps are used in Dijkstra's algorithm to find the shortest path in a weighted graph.
4. Huffman Coding: Heaps are used in Huffman coding, a widely used data compression technique.
5. Memory Management: In operating systems, heaps are used for dynamic memory allocation.
6. Event Scheduling: Heaps can be used to schedule events in time-based simulations or event-driven systems.
The most common operations on a heap are insertion and deletion of elements, which maintain the heap property. The complexity of insertion and deletion in a binary heap is O(log n), where n is the number of elements in the heap. This makes heaps very efficient for priority queue implementations and other applications that require efficient element insertion and removal based on priority.
IMPLEMENAION:
Below is a simple implementation of a binary max heap using C. In this implementation, we assume the elements of the heap are integers.
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
// Structure to represent the heap
struct Heap {
int array[MAX_HEAP_SIZE];
int size;
};
// Function to create a new empty heap
struct Heap* createHeap() {
struct Heap* heap = (struct Heap*)malloc(sizeof(struct Heap));
heap->size = 0;
return heap;
}
// Helper function to swap two elements in the heap
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to maintain the heap property (max heapify) at a given index
void maxHeapify(struct Heap* heap, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap->size && heap->array[left] > heap->array[largest])
largest = left;
if (right < heap->size && heap->array[right] > heap->array[largest])
largest = right;
if (largest != index) {
swap(&heap->array[index], &heap->array[largest]);
maxHeapify(heap, largest);
}
}
// Function to insert an element into the heap
void insert(struct Heap* heap, int value) {
if (heap->size == MAX_HEAP_SIZE) {
printf("Heap is full, cannot insert any more elements.\n");
return;
}
heap->array[heap->size] = value;
int current = heap->size;
heap->size++;
// Maintain the heap property by comparing the newly inserted element with its parent
while (current > 0 && heap->array[current] > heap->array[(current - 1) / 2]) {
swap(&heap->array[current], &heap->array[(current - 1) / 2]);
current = (current - 1) / 2;
}
}
// Function to extract the maximum element from the heap (root of the max heap)
int extractMax(struct Heap* heap) {
if (heap->size == 0) {
printf("Heap is empty, cannot extract any element.\n");
return -1;
}
int maxElement = heap->array[0];
heap->array[0] = heap->array[heap->size - 1];
heap->size--;
maxHeapify(heap, 0);
return maxElement;
}
// Function to print the elements of the heap
void printHeap(struct Heap* heap) {
printf("Heap elements: ");
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->array[i]);
}
printf("\n");
}
int main() {
struct Heap* heap = createHeap();
insert(heap, 10);
insert(heap, 20);
insert(heap, 5);
insert(heap, 15);
insert(heap, 30);
printHeap(heap);
int maxElement = extractMax(heap);
printf("Extracted max element: %d\n", maxElement);
printHeap(heap);
free(heap);
return 0;
}
```
OUTPUT:
Heap elements: 30 20 5 10 15
Extracted max element: 30
Heap elements: 20 15 5 10
Process returned 0 (0x0) execution time : 0.040 s
Press any key to continue.
Please note that this is a basic implementation to demonstrate the main operations of a max heap. In real-world scenarios, you might need to add error handling and additional functionalities as required.
0 Comments