堆的孩子和父親的下標(biāo)關(guān)系
已知父親(parent)的下標(biāo)
已知左孩子或右孩子下標(biāo)(child)
下面這個數(shù)組邏輯上可以看作是一棵完全二叉樹，通過從根節(jié)點(diǎn)開的向下調(diào)整算法可以把它調(diào)整成一個堆(大堆或小堆)，向下調(diào)整算法有以有一個前提：左右子樹必須是一個堆，才能調(diào)整。我這里的是實(shí)現(xiàn)小堆的向下調(diào)整算法。
建小堆的向下調(diào)整的基本思路就是：從堆頂開始，拿自己和較小的一個孩子進(jìn)行比較大小，如果小就進(jìn)行交換然后把交換的位置當(dāng)作父節(jié)點(diǎn)繼續(xù)向下調(diào)整，如果兩個孩子都比自己小就停止調(diào)整，否則一直調(diào)整到葉子節(jié)點(diǎn)。
重慶分公司
重慶分公司
// 向下調(diào)整(小堆)
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent+1;
while (parent< n)
{ //找出兩個孩子里的較小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿較小的孩子比較和父親比價大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //說明無需調(diào)整
break;
}
}
}堆的向下調(diào)整每次調(diào)整的一個節(jié)點(diǎn)，假設(shè)樹的高度為 h h h最壞情況下調(diào)整的次數(shù)就是 h ? 1 h-1 h?1，所以向下調(diào)整的時間復(fù)雜度就是樹的深度 l o g 2 ( n ? 1 ) log_{2}(n-1) log2?(n?1)，最后得出 l o g 2 n log_{2}n log2?n
堆的創(chuàng)建我們知道堆的向下調(diào)整算法必須滿足左右子樹都是一個堆，那有的時候是一個普通的數(shù)組，也就是一顆普通的完全二叉樹，所以要通過建堆來讓一個數(shù)組變成堆。
建堆的實(shí)現(xiàn)思路：從最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)，也就是第一個非葉子節(jié)點(diǎn)的父親開始不斷向下調(diào)整，直到整課樹都被調(diào)整成一個堆。
//向下調(diào)整建堆
int i = 0;
//從倒數(shù)第一個非葉子節(jié)點(diǎn)開始向下調(diào)整
for (i = (n - 2) / 2; i >= 0; --i)//n為數(shù)組元素個數(shù)
{AdjustDown(arr,n ,i);
}建堆的時間復(fù)雜度
我們知道時間復(fù)雜度就是計(jì)算最壞的時間復(fù)雜度，實(shí)際上就是計(jì)算一個滿二叉樹，這樣每一棵樹都會進(jìn)行調(diào)整。
假設(shè)這一棵樹的高度是 h h h
那么假設(shè)時間復(fù)雜度為 T n T_{n} Tn?，時間復(fù)雜度就是從第一層到倒數(shù)第二層每個節(jié)點(diǎn)的調(diào)整次數(shù)之和
所以建堆的時間復(fù)雜度就是 O ( N ) O(N) O(N)，因?yàn)楫?dāng) N N N足夠大時，對數(shù)的大小就根本不值得一提了。
堆的向上調(diào)整算法堆的向上調(diào)整算法是用一個堆中，當(dāng)我們要在堆的末尾插入一個新元素。
將堆頂元素和最后一個元素進(jìn)行交換，然后將最后一個位置的元素進(jìn)行向上調(diào)整。
如果是建小堆，拿最后一個元素和父節(jié)點(diǎn)進(jìn)行比較，如果父節(jié)點(diǎn)大于自己就進(jìn)行交換，接著以父節(jié)點(diǎn)的位置繼續(xù)開始向上調(diào)整，如果不小于父節(jié)點(diǎn)就停止向上調(diào)整(說明此時已經(jīng)滿足小堆的條件了)。
// 交換函數(shù)
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 向上調(diào)整(建小堆)
void AdjustUp(HPDataType* arr, int index)
{int child = index;
int parent = (child-1) / 2;//獲取父節(jié)點(diǎn)下標(biāo)
while (child >0)
{if (arr[parent] >arr[child])//如果節(jié)點(diǎn)如果大于孩子就交換
{ Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child-1) / 2;
}
else
{ //說明無需調(diào)整
break;
}
}
}通過一維數(shù)組來實(shí)現(xiàn)一個邏輯上的完全二叉樹，需要定義以下接口
堆的結(jié)構(gòu)體
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;//數(shù)組
int size;//堆中元素個數(shù)
int capacity;//堆的容量
}Heap;// 交換函數(shù)
void Swap(HPDataType* x, HPDataType* y);
// 堆的創(chuàng)建
Heap* HeapCreate(HPDataType* arr, int n);
// 向下調(diào)整
void AdjustDown(HPDataType* arr, int n, int index);
// 向上調(diào)整
void AdjustUp(HPDataType* arr, int index);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType data);
// 堆的刪除
void HeapPop(Heap* hp);
// 獲取堆頂元素
HPDataType HeapTop(Heap* hp);
// 獲取堆的元素個數(shù)
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);首先先通過malloc開辟空間
如果一個數(shù)組不是堆，在創(chuàng)建的時候就需要通過向下調(diào)整算法，從最后一個葉子節(jié)點(diǎn)的父親開始調(diào)整，把它調(diào)整成一個小堆
// 交換函數(shù)
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 堆的創(chuàng)建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下調(diào)整建堆
int i = 0;
//從倒數(shù)第一個非葉子節(jié)點(diǎn)開始向下調(diào)整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下調(diào)整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent + 1;
while (parent< n)
{ //找出兩個孩子里的較小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿較小的孩子比較和父親比價大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //說明無需調(diào)整
break;
}
}
}// 堆的插入
void HeapPush(Heap* hp, HPDataType data)
{assert(hp);
//擴(kuò)容
if (hp->size == hp->capacity)
{// 二倍擴(kuò)容
HPDataType* ptr = (HPDataType*)(realloc(hp->arr, sizeof(HPDataType)*hp->capacity * 2));
if (ptr == NULL)
{ printf("擴(kuò)容失敗\n %s", strerror(errno));
exit(-1);
}
hp->arr = ptr;
hp->capacity = 2 * hp->capacity;
}
hp->arr[hp->size] = data;
//向上調(diào)整
AdjustUp(hp->arr,hp->size);
hp->size++;
}刪堆頂元素實(shí)現(xiàn)思路
// 堆的刪除
void HeapPop(Heap* hp)
{//堆中沒有元素
assert(hp && hp->size != 0);
//拿堆頂元素和數(shù)組最后一個元素交換
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下調(diào)整
AdjustDown(hp->arr, hp->size, 0);
}這個比價簡單，就會返回數(shù)組 第一個元素就好
// 獲取堆頂元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}
// 獲取堆的元素個數(shù)
int HeapSize(Heap* hp)
{assert(hp);
return hp->size;
}// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);
return hp->size == 0;
}// 堆的銷毀
void HeapDestory(Heap* hp)
{assert(hp);
free(hp->arr);
hp->size = 0;
hp->capacity = 0;
hp->arr = NULL;
free(hp);
}Topk問題：給你一個組數(shù)據(jù)找出前k大的數(shù)
思路：對數(shù)組排序，取出前k個
size_t IntCmp(const void* x, const void* y)
{return *((int*)y) - *((int*)x);
}
void Test(int* arr, int n, int k)
{qsort(arr, n, sizeof(arr[0]), IntCmp);
int i = 0;
for (i = 0; i< k; i++)
{printf("%d ", arr[i]);
}
} qsort底層是通過快排實(shí)現(xiàn)的，而快排的時間復(fù)雜度為 n ? l o g 2 n n*log_{2}n n?log2?n
問題升級：能不能讓時間復(fù)雜度在降低一點(diǎn)
此時就可以通過堆來解決這個問題
假設(shè)前面的找前k個大的數(shù)，建個小堆，因?yàn)樾《训亩秧斠欢ㄊ鞘且唤M數(shù)里最小的一個數(shù)字，如果來了一個數(shù)字比最小的數(shù)還要大，那么它肯定是要先如堆的。
于是寫出代碼
// 堆的創(chuàng)建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下調(diào)整建堆
int i = 0;
//從倒數(shù)第一個非葉子節(jié)點(diǎn)開始向下調(diào)整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下調(diào)整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent;
while (parent< n)
{ //找出兩個孩子里的較小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿較小的孩子比較和父親比價大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent;
}
else
{ //說明無需調(diào)整
break;
}
}
}
// 堆的刪除
void HeapPop(Heap* hp)
{//堆中沒有元素
assert(hp && hp->size != 0);
//拿堆頂元素和數(shù)組最后一個元素交換
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下調(diào)整
AdjustDown(hp->arr, hp->size, 0);
}
// 獲取堆頂元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}然后不斷獲取堆頂元素，不斷刪除堆頂元素，就能得到前K個小的數(shù)。于是 O ( n ) O(n) O(n)的時間復(fù)雜就解決了問題
問題繼續(xù)升級：假設(shè)有100億個整數(shù)，從中找出前10大的數(shù)。
此時用單純用堆肯定行不通的，因?yàn)橐粋€整形4個字節(jié)，那么100億個整形就是400億個字節(jié)，那么這就是將近40G的數(shù)據(jù)，如果單純用堆肯定是不行的。
思路：建一個大小為10的小堆，不斷往堆中插入元素，如果元素滿了，就和堆頂比較，如果小就刪除堆頂元素，然后再進(jìn)行插入，直到遍歷完整個數(shù)組。
那么此時的時間復(fù)雜度為 O ( n ) O(n) O(n)，而空間復(fù)雜度則是 O ( k ) O(k) O(k)
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
