堆的概念與結(jié)構(gòu)

概念：如果有一個(gè)關(guān)鍵碼的集合 K={k0，k1 ，k2 ，…，kn-1}, 把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ) 在一個(gè)一維數(shù)組中，并滿足 K i<=K 2*i+1 且 Ki<=K 2*i+2 (K i>=K 2*i+1 且 Ki>=K 2*i+2) i = 0，1，2...，則稱為小堆 (或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

堆總是一棵完全二叉樹。

結(jié)構(gòu)：

1. 大堆

2. 小堆

 堆 (大根堆) 的實(shí)現(xiàn)：

堆的接口：

#pragma once

#include<stdio.h>

#include<stdlib.h>

#include<assert.h>

#include<stdbool.h>

typedef int HPDataType;

typedef struct Heap{
   HPDataType* a;    int size;    int capacity;
}HP;
//堆的創(chuàng)建void HeapInit(HP*hp);

//堆的銷毀void HeapDestroy(HP*hp);

//交換數(shù)值void Swap(HPDataType *px, HPDataType *py);

//向上調(diào)整void AdjustUp(int *a,int child);

//向下調(diào)整void AdjustDown(int *a, int n, int parent);

//堆的插入void HeapPush(HP*hp,HPDataType x);

//堆的刪除void HeapPop(HP*hp);

//取堆頂?shù)臄?shù)據(jù)HPDataType HeapTop(HP*hp);

//打印堆void HeapPrint(HP*hp);

//堆的判空bool HeapEmpty(HP*hp);

//堆的數(shù)據(jù)個(gè)數(shù)int HeapSize(HP*hp);

堆的創(chuàng)建：

void HeapInit(HP*hp)
{
   assert(hp);
   hp->a=NULL;
   hp->capacity=hp->size=0;
}

堆的銷毀：

void HeapDestroy(HP*hp){
   assert(hp);    free(hp->a);
   hp->capacity=hp->size=0;
}

交換數(shù)值：

void Swap(HPDataType*px, HPDataType*py){
   HPDataType tmp = *px;
   *px=*py;
   *py=tmp;
}

 向上調(diào)整：

void AdjustUp(int*a, int child){

assert(a);

int parent = (child - 1) / 2; while (child > 0)
{ if (a[child] > a[parent])
{            //交換數(shù)值
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
} else
{ break;
}
}
}

堆得插入：

void HeapPush(HP*hp,HPDataType x)
{
   assert(hp);    if(hp->capacity==hp->size)
   {
       size_t newCapacity=hp->capacity==0?4:hp->capacity*2;
       HPDataType * tmp=(HPDataType*)realloc(hp->a,newCapacity*sizeof(HPDataType));        if(tmp==NULL)
       {
           printf("realloc is fail\n");
       }
       hp->a=tmp;
       hp->capacity=newCapacity;
       
   }
   hp->a[hp->size-1]=x;
   hp->size++;    //向上調(diào)整
   AdjusiUp(hp->a,hp->size-1);
}

向下調(diào)整：

void AdjustDown(int *a,int n,int parent){    int child=parent*2+1;    while(child<n)
   {        //比較左孩子還是右孩子大
       if(child+1<n && a[child+1]>a[child])
       {
           child++;
       }        if(a[child]>a[parent])
       {
           Swap(&a[child],&a[parent]);
           parent=child;
           child=parent*2+1;
       }        else
       {            break;
       }
   }
}

堆的判空：

bool HeapEmpty(HP*hp){
   assert(hp);    return hp->size==0;
}

堆的刪除：

void HeapPop(HP*hp)
{
assert(hp);    //堆的判空
assert(!HeapEmpty(hp));    //交換數(shù)值
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;    //向下調(diào)整
AdjustDown(hp->a, hp->size, 0);
}

取堆頂?shù)臄?shù)據(jù)：

HPDataType HeapTop(HP*hp){    assert(hp);    assert(!HeapEmpty(hp));    return hp->a[0];
}

打印堆：

void HeapPrint(HP*hp){
   assert(hp);
   assert(!HeapEmpty(hp));    for(int i=0; i<hp->size;i++)
   {        printf("%d",hp->a[i]);
   }    printf("\n");
}

堆的數(shù)據(jù)個(gè)數(shù)：

int HeapSize(HP*hp){    assert(hp);    return hp->size;
}

以上就是對(duì)堆的講解與操作實(shí)現(xiàn)。