max heap Algorithm
The Max Heap algorithm is a specialized binary tree-based data structure that is widely used in numerous applications such as finding the maximum value in a dataset, sorting, and implementing priority queues. A Max Heap is essentially a complete binary tree with the unique property that the value of each parent node is greater than or equal to the values of its child nodes. This ensures that the highest value element is always present at the root of the tree. Max Heap allows for efficient search, insertion, and deletion operations, making it a highly versatile and powerful data structure.
To perform the Max Heap algorithm, the elements of a dataset are first arranged into a binary tree, ensuring that the tree is complete, i.e., every level of the tree is filled except for possibly the last level, which is filled from left to right. The algorithm then iteratively compares each parent node with its children, and if a child node is found to be greater than the parent, the two nodes are swapped. This process, known as "heapifying," is repeated until the entire tree satisfies the Max Heap property. Insertion and deletion operations in a Max Heap involve updating the tree to maintain the Max Heap property after the operation. Overall, the Max Heap algorithm offers an elegant and efficient way to manage large datasets, providing valuable insights and quick access to the maximum value in the dataset.
#include<stdio.h>
#include<stdlib.h>
typedef struct max_heap{
int *p;
int size;
int count;
}Heap;
Heap* create_heap(Heap* heap); /*Creates a max_heap structure and returns a pointer to the struct*/
void down_heapify(Heap* heap, int index);/*Pushes an element downwards in the heap to find its correct position*/
void up_heapify(Heap* heap, int index);/*Pushes an element upwards in the heap to find its correct position*/
void push(Heap* heap, int x);/*Inserts an element in the heap*/
void pop(Heap* heap);/*Removes the top element from the heap*/
int top(Heap* heap);/*Returns the top element of the heap or returns INT_MIN if heap is empty*/
int empty(Heap* heap);/*Checks if heap is empty*/
int size(Heap* heap);/*Returns the size of heap*/
int main(){
Heap* head = create_heap(head);
push(head, 10);
printf("Pushing element : 10\n");
push(head, 3);
printf("Pushing element : 3\n");
push(head, 2);
printf("Pushing element : 2\n");
push(head, 8);
printf("Pushing element : 8\n");
printf("Top element = %d \n", top(head));
push(head, 1);
printf("Pushing element : 1\n");
push(head, 7);
printf("Pushing element : 7\n");
printf("Top element = %d \n", top(head));
pop(head);
printf("Popping an element.\n");
printf("Top element = %d \n", top(head));
pop(head);
printf("Popping an element.\n");
printf("Top element = %d \n", top(head));
printf("\n");
return 0;
}
Heap* create_heap(Heap* heap){
heap = (Heap *)malloc(sizeof(Heap));
heap->size = 1;
heap->p = (int *)malloc(heap->size*sizeof(int));
heap->count = 0;
return heap;
}
void down_heapify(Heap* heap, int index){
if(index>=heap->count)return;
int left = index*2+1;
int right = index*2+2;
int leftflag = 0, rightflag = 0;
int maximum = *((heap->p)+index);
if(left<heap->count && maximum<*((heap->p)+left)){
maximum = *((heap->p)+left);
leftflag = 1;
}
if(right<heap->count && maximum<*((heap->p)+right)){
maximum = *((heap->p)+right);
leftflag = 0;
rightflag = 1;
}
if(leftflag){
*((heap->p)+left) = *((heap->p)+index);
*((heap->p)+index) = maximum;
down_heapify(heap, left);
}
if(rightflag){
*((heap->p)+right) = *((heap->p)+index);
*((heap->p)+index) = maximum;
down_heapify(heap, right);
}
}
void up_heapify(Heap* heap, int index){
int parent = (index-1)/2;
if(parent<0)return;
if(*((heap->p)+index)>*((heap->p)+parent)){
int temp = *((heap->p)+index);
*((heap->p)+index) = *((heap->p)+parent);
*((heap->p)+parent) = temp;
up_heapify(heap, parent);
}
}
void push(Heap* heap, int x){
if(heap->count>=heap->size)return;
*((heap->p)+heap->count) = x;
heap->count++;
if(4*heap->count >= 3*heap->size){
heap->size *= 2;
(heap->p) = (int *)realloc((heap->p), (heap->size)*sizeof(int));
}
up_heapify(heap, heap->count - 1);
}
void pop(Heap* heap){
if(heap->count==0)return;
heap->count--;
int temp = *((heap->p)+heap->count);
*((heap->p)+heap->count) = *(heap->p);
*(heap->p) = temp;
down_heapify(heap, 0);
if(4*heap->count<=heap->size){
heap->size /= 2;
(heap->p) = (int *)realloc((heap->p), (heap->size)*sizeof(int));
}
}
int top(Heap* heap){
if(heap->count!=0)return *(heap->p);
else return INT_MIN;
}
int empty(Heap* heap){
if(heap->count!=0)return 0;
else return 1;
}
int size(Heap* heap){
return heap->count;
}
