堆的概念與結構
概念：如果有一個關鍵碼的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉樹的順序存盤方式存盤 在一個一維陣列中，并滿足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...，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
性質：
- 堆中某個節點的值總是不大于或不小于其父節點的值；
- 堆總是一棵完全二叉樹，
結構：
1.大堆
2.小堆
堆(大根堆)的實作：
堆的介面：
#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;
//堆的創建
void HeapInit(HP*hp);
//堆的銷毀
void HeapDestroy(HP*hp);
//交換數值
void Swap(HPDataType *px, HPDataType *py);
//向上調整
void AdjustUp(int *a,int child);
//向下調整
void AdjustDown(int *a, int n, int parent);
//堆的插入
void HeapPush(HP*hp,HPDataType x);
//堆的洗掉
void HeapPop(HP*hp);
//取堆頂的資料
HPDataType HeapTop(HP*hp);
//列印堆
void HeapPrint(HP*hp);
//堆的判空
bool HeapEmpty(HP*hp);
//堆的資料個數
int HeapSize(HP*hp);
堆的創建：
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;
}交換數值：
void Swap(HPDataType*px, HPDataType*py)
{
HPDataType tmp = *px;
*px=*py;
*py=tmp;
}向上調整：
void AdjustUp(int*a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//交換數值
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++;
//向上調整
AdjusiUp(hp->a,hp->size-1);
}向下調整：
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));
//交換數值
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
//向下調整
AdjustDown(hp->a, hp->size, 0);
}取堆頂的資料：
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");
}堆的資料個數：
int HeapSize(HP*hp)
{
assert(hp);
return hp->size;
}以上就是對堆的講解與操作實作，
感謝老鐵看到這里，如果文章對你有用的話請給我一個贊支持一下，感激不盡！
在下才疏學淺,一點淺薄之見，歡迎各位大佬指點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352217.html
標籤：其他