堆的使用
- 1.堆的基本介紹
- 2.堆向下調整演算法
- 3.堆排序
- 4.資料結構實作堆
- 堆的初始化
- 插入資料
- 洗掉資料
- 堆的銷毀
- 堆的資料個數
- 取堆頂的資料
- 堆的判斷空
1.堆的基本介紹
1.物理結構是一個陣列
2.邏輯結構是完全二叉樹
3.大堆（樹中所有的父親大于等于孩子） 小堆（樹中所有的父親小于等于孩子）
完全二叉樹每一層有2^n個樹叉
父子間關系：
leftchild=parent2+1
rightchild=parent2+2
parent=(child-1)/2
2.堆向下調整演算法
注意 : 向下調整演算法的前提是左右子樹必須是堆(小堆/大堆)
建堆，選出左右孩子中小的那一個，
堆分小根堆和大根堆兩類
這里我們以小根堆為例，
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[parent], &a[child]);
child = parent * 2 + 1;
}
else
{
break;
}
}
}
3.堆排序
堆排序優于直接選擇排序->o(n^2)才有價值
1.建堆o(N)
2.繼續選數
如果排升序建小堆，問題在于：選出最小的數放到第一個位置，緊接著要選出次小的，如何選？
如果沒搞一個都要通過建堆來選 數，還不如直接遍歷比較來選數，堆排序就沒有意義了，
所以排升序優先建大堆，
void HeapSort(int *a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
//選出次大的
AdjustDown(a, end, 0);
--end;
}
}
結論：堆排序的時間復雜度o(N*logN).
4.資料結構實作堆
堆的初始化
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof((HPDataType)*n);
php->size = n;
php->capacity = n;
}
插入資料
我們將資料插入到堆陣列的末尾，在進行向上調整，
void AdjustUp(int* a,int child)
{
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* php, HPDataType x)
{
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
HPDataType[php->size-1] = x;
php->size++;
Adjustup(php->a,php->size-1,x);
}
}
洗掉資料
和上面堆排序的思想類似，將堆頂的資料和最后一個資料換位，洗掉最后一個資料，再進行向下調整演算法，
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
Swap(&hp->_a[0],&hp->_a[hp->_size - 1]);
hp->size--;
AdjustDown(hp->_a,0,hp->size)
}
堆的銷毀
void HeapDestroy(Heap* hp)
{
assert(hp);
free(hp->_a);
free(hp);
}
堆的資料個數
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;
}
取堆頂的資料
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
return hp->_a[0];
}
堆的判斷空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->_size == 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295403.html
標籤：其他