Introduction to basic heap based operations

We expect a data structure that supports insertion and makes it easy to extract records with the smallest or largest keys from them, known as a priority queue. Of the various implementations of priority queues, the heap is the most efficient data structure.
The minimum heap: The key code of any node is less than or equal to the key code of its left and right children, and the key code of the node at the top of the heap is the minimum of the whole set of elements, so it is called the minimum heap. Maximum number of similar definitions.

Create a heap: The heap is created by gradually adjusting the heap from the bottom up. Call the down call algorithm siftDown for the following branch nodes to adjust the subtree with them as root to the minimum heap. From the local to the whole, the minimum heap is gradually expanded until the entire tree is adjusted to the minimum heap.

Insert an element: The insertion algorithm of the minimum heap calls another heap adjustment method, siftUp, to realize the upward sliding adjustment from bottom to top. Because every time a new node is inserted behind the smallest heap that has been built, you must follow the comparison path opposite to sift, from the bottom up, to the parent's key, and switch.

Delete an element: Removed from the minimum pile when operating with least key records will be minimum heap heap top elements, namely the complete binary tree order said element number 0 delete, to take off this element, general with pile was the last node fill take roof element, and the heap of the actual element number minus 1. But the last element to replace the pile top element will destroy the heap, you need to call siftDown algorithm to adjust the heap.

The code in this article takes the implementation of the minimum heap as an example.

#include<iostream>
#include<assert.h>
usingnamespace std;
constint maxheapsize=100;
staticint currentsize=0;
//Adjust the heap from top to bottom
void siftDown(int* heap,int currentPos,int m)
{
    int i=currentPos;
    int j=currentPos*2+1;//i's leftChild
int temp=heap[i];
    while(j<=m)
    {
        if(j<m&&heap[j]>heap[j+1]) j++;// j points to minChild
if(temp<=heap[j]) break;
        else 
        {
            heap[i]=heap[j];
            i=j;
            j=2*i+1;
        }
    }
    heap[i]=temp;
}
//Adjust the heap from the bottom up
void siftUp(int* heap, int start)
{
    int i=start,j=(i-1)/2;
    int temp=heap[i];
    while(i>0)
    {
        if(heap[j]>temp) 
        {
            heap[i]=heap[j];
            i=j;
            j=(i-1)/2;
        }
        elsebreak;
    }
    heap[i]=temp;
}
//Building the heap
int* Heap(int*arr, int size)
{
    int i;
    currentsize=size;
    int* heap =newint[maxheapsize];
    assert(heap!=NULL);
    for(i=0;i<currentsize;i++) heap[i]=arr[i];
    int currentPos=(currentsize-2)/2;
    while(currentPos>=0)
    {
        siftDown(heap,currentPos,currentsize-1);
        currentPos--;
    }
    return heap;
}

//Add an element
void insert(int* heap,int value)
{
    if(currentsize>=maxheapsize)
    {
        cout<<"Heap is full!"<<endl;
        return ;
    }
    heap[currentsize]=value;
    siftUp(heap,currentsize);
    currentsize++;
}
//Deletes an element and returns the previous heap top element
int removemin(int* heap)
{
    assert(currentsize>=0);
    int removeValue=heap[0];
    heap[0]=heap[currentsize-1];
    currentsize--;
    siftDown(heap,0,currentsize-1);
    return removeValue;
}
int main()
{
    constint size=10;
    int arr[size]={2,1,3,0,8,1,6,9,7,10};
    int* heap=Heap(arr,size);
    //Heap sort
for(int i=0;i<size;i++)
    {
        arr[i]=removemin(heap);
        cout<<arr[i]<<endl;
    }
    delete []heap;
    return0;

 
 
}