快捷導航

基于堆的基本操作的介紹

更新時間：2013年05月07日 11:23:03 作者：

本篇文章對堆的基本操作進行了詳細的分析介紹。需要的朋友參考下

　　我們期望的數(shù)據(jù)結(jié)構(gòu)能支持插入操作，并能方便地從中取出具有最小或最大關(guān)鍵碼的記錄，這樣的數(shù)據(jù)結(jié)構(gòu)即為優(yōu)先級隊列。在優(yōu)先級隊列的各種實現(xiàn)中，堆是最高效的一種數(shù)據(jù)結(jié)構(gòu)。
　　最小堆：任一結(jié)點的關(guān)鍵碼均小于或等于它的左右子女的關(guān)鍵碼，位于堆頂?shù)慕Y(jié)點的關(guān)鍵碼是整個元素集合的最小的，所以稱它為最小堆。最大堆類似定義。

　　創(chuàng)建堆：采用從下向上逐步調(diào)整形成堆得方法來創(chuàng)建堆。為下面的分支結(jié)點調(diào)用下調(diào)算法siftDown，將以它們?yōu)楦淖訕湔{(diào)整為最小堆。從局部到整體，將最小堆逐步擴大，直到將整個樹調(diào)整為最小堆。

　　插入一個元素：最小堆的插入算法調(diào)用了另一種堆得調(diào)整方法siftUp，實現(xiàn)自下而上的上滑調(diào)整。因為每次新結(jié)點總是插在已經(jīng)建成的最小堆后面，這時必須遵守與sift相反的比較路徑，從下向上，與父結(jié)點的關(guān)鍵碼進行比較，對調(diào)。

　　刪除一個元素：從最小堆刪除具有最小關(guān)鍵碼記錄的操作時將最小堆的堆頂元素，即其完全二叉樹的順序表示的第0號元素刪去，去把這個元素取走后，一般以堆得最后一個結(jié)點填補取走的堆頂元素，并將堆的實際元素個數(shù)減1.但是用最后一個元素取代堆頂元素將破壞堆，需要調(diào)用siftDown算法進行調(diào)整堆。

本文代碼均以最小堆的實現(xiàn)為例。

復制代碼代碼如下:

#include<iostream>
#include<assert.h>
usingnamespace std;

constint maxheapsize=100;
staticint currentsize=0;

//從上到下調(diào)整堆
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;
}

//從下向上調(diào)整堆
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;
}

//構(gòu)建堆
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;
}

//增加一個元素
void insert(int* heap,int value)
{
    if(currentsize>=maxheapsize)
    {
        cout<<"Heap is full!"<<endl;
        return ;
    }
    heap[currentsize]=value;
    siftUp(heap,currentsize);
    currentsize++;
}

//刪除一個元素,并返回刪除前的堆頂元素
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);
    //堆排序
for(int i=0;i<size;i++)
    {
        arr[i]=removemin(heap);
        cout<<arr[i]<<endl;
    }
    delete []heap;
    return0;

}