二叉樹的順序結構及實作
- 1. 二叉樹的順序結構
- 2. 堆的概念及結構
- 3. 堆的實作
- 3.1 堆向下調整演算法
- 3.2 堆排序
- 3.2.1 堆排序完整代碼
- 3.3 堆的插入
- 3.3.1 堆的向上排序演算法
- 3.4 堆的洗掉
- 4. 完整堆代碼
- 5.topK問題
- 5.1 劍指offer第40題---最小的K個數
1. 二叉樹的順序結構
普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，
2. 堆的概念及結構
如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，(簡單點說就是所有的孩子都大于雙親結點的值稱為小堆----就是要把最小的不停的往上浮，所有的孩子都小于雙親結點的值稱為大堆—就是要把最大的值不停的向上浮)
堆的性質：
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，
3. 堆的實作
3.1 堆向下調整演算法
現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，
int a[] = {27,15,19,18,28,34,65,49,25,37};
左右子樹是一個小堆的特點，就可以使用向下調整演算法，進行調整，
//交換
void Swap(HPDateType* p1,HPDateType* p2)
{
HPDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下調整演算法
//前提：左右子樹都是小堆
void AdjustDown(HPDateType* a, int n, int root)
{
//這個root表示從哪里開始調整的位置
int parent = root;
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//找出左右孩子中小的那一個
//這是一個完全二叉樹，右孩子可能是不存在的，所以child +1 有可能是會越界的
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;
}
}
}
3.2 堆排序
有了向下調整演算法就可以考慮實作堆排序的問題！
但是你要使用向下調整演算法的前提應該保證他的左右子樹都是小堆，所以初始化要先完成，
void HeapInit(Heap* php, HPDateType* a, int n)
{
php->_a = (HPDateType)malloc(sizeof(HPDateType)*n);
if (php->_a == NULL)
{
printf("記憶體不足\n");
exit(-1);
}
memcpy(php->_a, a, sizeof(HPDateType)*n); //我有一個陣列，我一上來就希望你把這個陣列里面的值都放在你所開辟的這個堆里面
php->_size = n;
php->_capacity = n;
//你把陣列的元素都放在了你所開辟的陣列空間里面就是堆了嗎？
//顯然目前還不是堆
//構建小堆
//首先保證左右子樹都是小堆的情況下才能進行向下調整演算法的操作
//但是這里進行調整左右子樹的時候要從最下面開始調起（倒著來）
//把每一個三角都看作是一個小堆，進行調整
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(php->_a, php->_size, i);
}
}
這里就有思考的問題：堆排序的時間復雜度是多少？為什么要使用堆排序
void HeapSort(int* a, int n)
{
//建堆
//這里可以i=n-1開始調，也就是最后一個位置開始調整，但是你會發現那些都是葉子，你算他的孩子（但是它壓根就沒有孩子，所以這里對葉子進行向下調整是沒有意義的，應該從他的最后一個雙親結點開始調整）
//這里的n-1表示陣列的最后一個元素下角標，然后帶入知道孩子求雙親結點下角標的公式中
for (int i = (n - 1-1)/2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
}
int main()
{
int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
HeapSort(a, sizeof(a) / sizeof(HPDateType));
return 0;
}
因為你并沒有規定左右孩子誰大誰小，所以堆排序一次并不是有序的，但是你會發現堆排序一次以后你選出了小堆里面最小的哪一個，
堆排序的時間復雜度為多少？，為什么要使用堆排序的？
對于一個滿二叉樹來說是件復雜度就是樹的高度h=Log(N+1) 這里表示以2為底，N+1為對數，對于完全二叉樹來說h=LogN 這里表示以2為底，N為對數，對于堆排序的時間復雜度是N * O(LogN）這里可以參考文章：鏈接: link.
解釋：你每一次使用向下調整演算法得到一個最小的數的時間復雜度就是其高度h=LogN，但是你一共有N個數需要遍歷，所以堆排序的時間復雜度是N * LogN
你會發現堆排序的時間復雜度要小的多，那么當你需要排序的數字非常大的時候，他可以為你節省很多時間，（如果你每一次選出最小的數以后，在以這個小堆根結點的下一個數作為新的根結點，重新進行一次堆排序，不但會破壞掉原來的結構，而且時間復雜度為O(N*N) )
那么如果你想要的這個堆里面的次小的數如何得到呢？
排降序：建小堆
堆排序完一次以后可以選出最小的哪一個數，然后讓他和陣列的最后一個元素交換，陣列在縮短一個（相當于把最小的那個數排除在外），重新進行一次堆排序，不斷重復，就會得到一個降序的陣列，從而得到次小的數，
排升序：建大堆，進行和上面相同的步驟（只需要把大孩子往上浮就行）
3.2.1 堆排序完整代碼
void HeapSort(int* a, int n)
{
//建堆
//這里可以i=n-1開始調，也就是最后一個位置開始調整，但是你會發現那些都是葉子，你算他的孩子（但是它壓根就沒有孩子）
for (int i = (n - 1-1)/2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1; //end代表的陣列里面的元素個數
while (end>0)
{
Swap(&a[0], &a[end]);
//在繼續選次小的
AdjustDown(a, end, 0);
end--;
}
}
int main()
{
int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
HeapSort(a, sizeof(a) / sizeof(HPDateType));
return 0;
}
3.3 堆的插入
這里一定要深刻記住完全二叉樹的定義，你要往這個堆里面插入資料，應該在那個位置插入，
本來你這里的左右子樹都是小堆，但是你現在插入的是一個大于父親的數那么依舊保持著小堆的特點，但是你在這里如果插入的是一個小于父親的數，則這里就不在保持小堆的特點，所以需要堆的向上排序演算法
3.3.1 堆的向上排序演算法
void AdjustUp(HPDateType* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child > 0) //因為當child=0的時候，此時parent早已經小于0了，想不通的話，自己畫個堆來看
{
if (a[child] < a[parent])
{
//這里考慮的是如果你插入的這個數比父親要小，說明此時你不能保持小堆的特點，需要交換
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* php, HPDateType x)
{
//這里一定要深刻記住完全二叉樹的定義，你要往這個堆里面插入資料，應該在那個位置插入
//本來你這里的左右子樹都是小堆，但是你現在插入的是一個大于父親的數那么依舊保持著小堆的特點，但是你在這里如果插入的是一個小于父親的數
//此時你的小堆的特點就不對了，你應該怎么辦？（需要處理了）
//堆這個特點就是借助陣列的下標來表示父子關系的
//所以此時這里需要一個向上調整演算法
assert(php);
//只要是順序表的加入資料就要考慮到是否需要增容
if (php->_size == php->_capacity)
{
php->_capacity *= 2;
HPDateType* tmp = (HPDateType*)realloc(php->_a, sizeof(HPDateType)*php->_capacity);
if (tmp == NULL)
{
printf("開辟失敗\n");
exit(-1);
}
else
{
php->_a = tmp;
}
}
php->_a[php->_size++] = x; //這里的++是后置的，先會使用php->_size然后使用完了之后才會++，因為你的size是有效的資料也在不斷的增加
AdjustUp(php->_a, php->_size, php->_size - 1);
}
3.4 堆的洗掉
需要洗掉的是堆頂的數值，
void HeapPop(Heap* php) //因為只有干掉堆頂的這個最小的值，你才有機會找到次小的數
{
//這里的pop的目的是洗掉掉堆頂的資料
//你要明白一旦改變了堆頂的資料，就會發現整個結構就會發生改變，父子關系什么的都會重新
assert(php);
assert(php->_size > 0);// 如果這里都沒有資料了你還在那里刪什么
Swap(php->_a[0], php->_a[php->_size - 1]);
php->_size--;//這里是真的要干掉堆頂這個資料
AdjustDown(php->_a, php->_size, 0);
}
4. 完整堆代碼
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
typedef int HPDateType;
//小堆
typedef struct Heap
{
HPDateType* _a;
int _size;
int _capacity;
}Heap;
void AdjustDown(HPDateType* a, int n, int root);
void AdjustUp(HPDateType* a, int n, int child);
void HeapInit(Heap* php, HPDateType* a, int n);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HPDateType x);
void HeapPop(Heap* php);
HPDateType HeapTop(Heap* php);
#include"Heap.h"
//交換
void Swap(HPDateType* p1,HPDateType* p2)
{
HPDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下調整演算法
//前提：左右子樹都是小堆
void AdjustDown(HPDateType* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//找出左右孩子中小的那一個
//這是一個完全二叉樹，右孩子可能是不存在的，所以child +1 有可能是會越界的
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;
}
}
}
void HeapInit(Heap* php, HPDateType* a, int n)
{
php->_a = (HPDateType)malloc(sizeof(HPDateType)*n);
if (php->_a == NULL)
{
printf("記憶體不足\n");
exit(-1);
}
memcpy(php->_a, a, sizeof(HPDateType)*n); //我有一個陣列，我一上來就希望你把這個陣列里面的值都放在你所開辟的這個堆里面
php->_size = n;
php->_capacity = n;
//但是目前還不是堆，你只是把陣列里面的內容都放在了這里面
//構建堆
//首先保證左右子樹都是小堆的情況下才能進行向下調整演算法的操作
//但是這里進行調整左右子樹的時候要從最下面開始調起（倒著來）
//把每一個三角都看作是一個小堆，進行調整
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(php->_a, php->_size, i);
}
}
void AdjustUp(HPDateType* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child > 0) //因為當child=0的時候，此時parent早已經小于0了，想不通的話，自己畫個堆來看
{
if (a[child] < a[parent])
{
//這里考慮的是如果你插入的這個數比父親要小，說明此時你不能保持小堆的特點，需要交換
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapDestory(Heap* php)
{
assert(php);
free(php->_a);
php->_a = NULL;
php->_size = php->_capacity = 0;
}
void HeapPush(Heap* php, HPDateType x)
{
//這里一定要深刻記住完全二叉樹的定義，你要往這個堆里面插入資料，應該在那個位置插入
//本來你這里的左右子樹都是小堆，但是你現在插入的是一個大于父親的數那么依舊保持著小堆的特點，但是你在這里如果插入的是一個小于父親的數
//此時你的小堆的特點就不對了，你應該怎么辦？（需要處理了）
//堆這個特點就是借助陣列的下標來表示父子關系的
//所以此時這里需要一個向上調整演算法
assert(php);
//只要是順序表的加入資料就要考慮到是否需要增容
if (php->_size == php->_capacity)
{
php->_capacity *= 2;
HPDateType* tmp = (HPDateType*)realloc(php->_a, sizeof(HPDateType)*php->_capacity);
if (tmp == NULL)
{
printf("開辟失敗\n");
exit(-1);
}
else
{
php->_a = tmp;
}
}
php->_a[php->_size++] = x; //這里的++是后置的，先會使用php->_size然后使用完了之后才會++，因為你的size是有效的資料也在不斷的增加
AdjustUp(php->_a, php->_size, php->_size - 1);
}
void HeapPop(Heap* php) //因為只有干掉堆頂的這個最小的值，你才有機會找到次小的數
{
//這里的pop的目的是洗掉掉堆頂的資料
//你要明白一旦改變了堆頂的資料，就會發現整個結構就會發生改變，父子關系什么的都會重新
assert(php);
assert(php->_size > 0);// 如果這里都沒有資料了你還在那里刪什么
Swap(php->_a[0], php->_a[php->_size - 1]);
php->_size--;//這里是真的要干掉堆頂這個資料
AdjustDown(php->_a, php->_size, 0);
}
HPDateType HeapTop(Heap* php)
{
//取堆頂的資料，就是0的位置
assert(php);
assert(php->_size > 0);
return php->_a[0];
}
5.topK問題
N個數中找出最大的或者最小的前K個數，
5.1 劍指offer第40題—最小的K個數
鏈接: link.
解題思路：我取陣列中的前k個數構建一個大堆，那么這個大堆的堆頂就是我所選出來的這k個數中最大的一個數，然后我讓沒有進入堆的數去和堆頂比較（大的數我是不想要的，因為我在找小的數，所以直接把大的數替換掉）最后你所剩下的這個大堆就是一個最小的前k個數所構建的大堆，剛好這個堆頂就是最大的數，通過這個思想還可以去考慮解決別的題目，
牛客網中也有這道題，最小的k個數，
鏈接: link.
牛客網：尋找第K大的數，
思想和這道題的解題思路類似，當好你最后所構建的前k個數的大堆的堆頂，就是我要找的第K個大的數，
鏈接: link.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void Swap(int* p1,int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int* a,int n,int root)
{
int parent = root;
int child = parent*2 + 1;//這個是左孩子的下角標,我就假設他是兩個孩子中較大的那一個
while(child < n)//想的是結束的條件，但寫的要是繼續的條件，當你的parent到最后一個葉子結點處，此時你的孩子就越陣列了
{
//確保選出兩個孩子中較大的那一個
if(child+1 < n && a[child+1]>a[child])
{
child++;
}
if(a[child]>a[parent])
{
Swap(&a[child],&a[parent]);
//讓其迭代起來，不要忘記他是向下調整演算法，這里的root是從父親結點開始調整的
parent = child;
child = parent*2 + 1;
}
else
{
break;
}
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
*returnSize = k;
//說明你要找的數就沒有，回傳的空的是一個空陣列
if(k == 0)
return NULL;
int* retArr = (int*)malloc(sizeof(int)*k);
//建k個數的大堆
for(int i = 0;i<k;i++)
{
retArr[i] = arr[i]; //我直接把陣列里面的k個數拿到我所創建的這個所謂堆（此時還不能叫堆，或許不滿足堆特點）里面，此時并不能保證最小的就在這個里面
}
//從他的最后一個雙親結點開始調整
for(int i = (k-1-1)/2;i>=0;--i)
{
AdjustDown(retArr,k,i);
} //此時你的大堆就已經構建完成了，你前k個數中最大的數就在堆頂，而小的數都在最下面
//除了那K個數剩下的數
for(int j = k;j < arrSize;j++)
{
//我要的是前k個小的數，我不要大的數，大的數可以直接被踢掉
if(arr[j]<retArr[0])
{
retArr[0] = arr[j];
AdjustDown(retArr,k,0);
}
//最后遍歷完剩下的K-1個數，只要是前k個小的數，最后都會進堆
}
return retArr;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/248640.html
標籤：其他