Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Delete operation

Process analysis

First we give the name of the function and its arguments.

int deleteheap( int heap[])
Copy the code

In this case, deletion refers to the removal of heap[1], which is the top of the heap.

Suppose the heap looks like this:

Heap [6]={6,1,3,4,8,7,6},len=6.

After a delete operation, the last bit of the heap array is placed in the heap[0] and len length is reduced by one.

When we observe the structure of the heap, we can see that 6 is larger than its child nodes 4 and 5. So we still need to carry out structural adjustment work.

After sinking 6, the structure of the final heap is shown as follows:

Code implementation

1. Delete child nodes

heap[1]=heap[len];
	len--;
Copy the code

2. Sink the newly set top node of the heap

	while(1) {// Loop exit condition
		if(2*i>len){
			break;
		}
		if(heap[i]>heap[2*i] && heap[2*i]<heap[2*i+1]){
			temp=heap[i];
			heap[i]=heap[2*i];
			heap[2*i]=temp;
			i=2*i;
		}
		else if(heap[i]>heap[2*i+1] && heap[2*i+1]<heap[2*i]){
			temp=heap[i];
			heap[i]=heap[2*i+1];
			heap[2*i+1]=temp;
			i=2*i+1;
		}else
			break;
	}
Copy the code

Function code synthesis

// Delete the first element
int deleteheap( int heap[]){
	heap[1]=heap[len];
	len--;
	int temp;
	int i=1;
	while(1) {// Loop exit condition
		if(2*i>len){
			break;
		}
		if(heap[i]>heap[2*i] && heap[2*i]<heap[2*i+1]){
			temp=heap[i];
			heap[i]=heap[2*i];
			heap[2*i]=temp;
			i=2*i;
		}
		else if(heap[i]>heap[2*i+1] && heap[2*i+1]<heap[2*i]){
			temp=heap[i];
			heap[i]=heap[2*i+1];
			heap[2*i+1]=temp;
			i=2*i+1;
		}else
			break;
	}
	return heap[1]; 
} 
Copy the code

Display of code and results for heap operations

#include<stdio.h>
int heap[10] = {5.1.3.4.5.7};
int len;

// Insert x into the heap
void insert( int x, int heap[]){
	int i=len+1;
	len++;
	heap[i]=x;
	while(i>1) {if(heap[i]<heap[i/2]){
			int temp=heap[i];
			heap[i]=heap[i/2];
			heap[i/2]=temp;
		}
		else
			break;
		
		i=i/2; }}// Update pos to x
void update(int x, int pos, int heap[]){
	heap[pos]=x;
	int i=pos;
	while(1) {// Loop exit condition
		if(i<=1||2*i>len){
			break;
		}
		
		int temp;
		// Float up if it is smaller than the parent node
		if(heap[i]<heap[i/2]){
			temp=heap[i];
			heap[i]=heap[i/2];
			heap[i/2]=temp;
			i=i/2;
		}else if( (heap[i]>heap[2*i]&&heap[2*i]<heap[2*i+1) | |2*i+1>len ){// Sink if it is larger than the child node
			temp=heap[i];
			heap[i]=heap[2*i];
			heap[2*i]=temp;
			i=2*i;
		}else if(heap[i]>heap[2*i+1]&&heap[2*i+1]<heap[2*i]){
			temp=heap[i];
			heap[i]=heap[2*i+1];
			heap[2*i+1]=temp;
			i=2*i+1; }}}// Delete the first element
int deleteheap( int heap[]){
	heap[1]=heap[len];
	len--;
	int temp;
	int i=1;
	while(1) {// Loop exit condition
		if(2*i>len){
			break;
		}
		if(heap[i]>heap[2*i] && heap[2*i]<heap[2*i+1]){
			temp=heap[i];
			heap[i]=heap[2*i];
			heap[2*i]=temp;
			i=2*i;
		}
		else if(heap[i]>heap[2*i+1] && heap[2*i+1]<heap[2*i]){
			temp=heap[i];
			heap[i]=heap[2*i+1];
			heap[2*i+1]=temp;
			i=2*i+1;
		}else
			break;
	}
	return heap[1]; 
} 


/ / output heap
void print(int heap[]){
	printf("len=%d\n",len);
	int i=1;
	while(i<=len){
		printf("%d ",heap[i++]);
	}
	printf("\n");
} 
int main(){

	len=5;
	printf("Raw heap \n");
	print(heap);
	insert(2,heap);
	printf("After adding operation: \n"); 
	print(heap);
	update(6.3,heap); 
	printf("After Update operation 1: \n");
	print(heap);
	update(8.4,heap);
	printf("After Update operation 2: \n");
	print(heap);
	int now=deleteheap(heap);
	printf("After delete operation: \n");
	printf("Heap top element: %d\n",now);
	print(heap);
	return 0;
} 
Copy the code