堆
文章目錄
- 堆
- 一、堆的概念
- 二、堆的實作
- 1. 定義節點
- 2. 堆的初始化
- 3. 堆的銷毀
- 4. 堆的插入
- 5. 堆的洗掉
一、堆的概念
堆是二叉樹的一種特殊情況
-
一個堆中的所有節點的值總是不大于或不小于其父節點的值
-
堆是一棵完全二叉樹，
-
堆分為大堆和小堆
大堆：
根節點最大的堆叫做最大堆或大根堆
小堆：
根節點最小的堆叫做最小堆或小根堆
普通的二叉樹是不適合用陣列來存盤，因為可能會因為資料不連續而導致存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，
又因為上一篇文章中提出【資料結構】二叉樹的定義以及性質_Rinne’s blog-CSDN博客
子節點和父節點序號有一定的聯系
這里的堆，我們用陣列來實作
二、堆的實作
1. 定義節點
我們先確定了用陣列的形式來實作，雖然物理上是一個順序表的樣子，但邏輯上我們使用的程序它卻是一個堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
2. 堆的初始化
本質上就是順序表的初始化
//堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}
3. 堆的銷毀
本質上是順序表的銷毀
// 堆的銷毀
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->capacity = hp->size = 0;
}
4. 堆的插入
前面還是跟順序表一樣，插入之前先判斷記憶體空間夠不夠，不夠就malloc
關鍵在于：
- 如果是一個
大堆，插入的數比它的父節點大，我們需要去向上調整 - 如果是一個
小堆，插入的數比它的父節點小，我們需要去向上調整
先看大堆
如果子節點比父節點大，交換父子節點
當子節點序號為0時候停止
以下是大堆，小堆需要改一下＞符號
//交換資料
void swap(HPDataType* parent, HPDataType* child)
{
HPDataType tmp = *child;
*child = *parent;
*parent = tmp;
}
//向上調整
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (a[child] > a[parent] && child != 0)
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
exit(-1);
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1);
}
測驗：
void test1()
{
Heap h;
HeapInit(&h);
HeapPush(&h, 24);
HeapPush(&h, 11);
HeapPush(&h, 9);
HeapPush(&h, 1);
HeapPush(&h, 2);
HeapPush(&h, 6);
HeapPush(&h, 30);
int i = 0;
for (i = 0; i < h.size; i++)
{
printf("%d ", h.a[i]);
}
}
測驗結果： 可以看出后面插入的30被向上調整到前面去了
5. 堆的洗掉
洗掉堆是洗掉堆頂的資料
還是以剛才的例子為例
將堆頂的資料根最后一個資料一換，然后洗掉陣列最后一個資料
為什么不直接洗掉根呢，根是陣列的頭，類似順序表的頭刪，需要把所有元素向前移動，這就改變了整個樹的相對位置，時間復雜度為o(n)，而洗掉了根之后，我們需要調整位置，找到下一個根，根的子節點，為左右兩個孩子，
挑出左右孩子中最大的那個
再進行 向下調整演算法
//向下調整
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (a[child] < a[child + 1] && child + 1 < n)
{
child++;
}
if (a[parent] < a[child])
{
swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆的洗掉
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size);
swap(&hp->a[0], &(hp->a[hp->size - 1]));
hp->size--;
//刪完后開始調整
AdjustDown(hp->a, hp->size, 0);
}
在插入的測驗代碼基礎上再洗掉根
測驗結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350936.html
標籤：其他
上一篇：劍指offer-之-鏈表
下一篇：資料結構初階：堆疊和佇列