目錄
堆的概念及結(jié)構(gòu)
?編輯
堆的實現(xiàn)?
實現(xiàn)堆的接口
堆的初始化
堆的打印
堆的銷毀
獲取最頂?shù)母鶖?shù)據(jù)
?交換
堆的插入（插入最后）
向上調(diào)整（這次用的是小堆）
堆的刪除（刪除根）
向下調(diào)整（這次用的小堆）
堆排序
TOP-K問題
堆的概念及結(jié)構(gòu)
如果有一個關(guān)鍵碼的集合
K = {
， ， ，
…
，}，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足： <= 且 <= ( >= 且 >= ) i = 0，
1
， 2…，則稱為小堆
(
或大堆
)
。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
- 堆總是一棵完全二叉樹。
小根堆：父親節(jié)點大于等于孩子節(jié)點
大根堆：父親節(jié)點小于等于孩子節(jié)點?
堆的實現(xiàn)?
實現(xiàn)堆的接口
#define CRT_SECURE_NO_WARNING 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
//二叉樹-堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
//交換
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//銷毀
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//刪除
void HeapPop(HP* php);
//返回最頂數(shù)據(jù)
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);堆的初始化
//初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}堆的打印
void HeapPrint(HP* php)
{
assert(php);
//最后一個孩子下標為size-1
for (size_t i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
堆的銷毀
//銷毀
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}獲取最頂?shù)母鶖?shù)據(jù)
//獲取根數(shù)據(jù)
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
?交換
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}堆的插入（插入最后）
先考慮擴容，將數(shù)據(jù)插到最后，再用向上調(diào)整法。
//插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//擴容
if (php->size == php->capacity)//有效元素個數(shù)和容量是否相等
{
//相等的情況分兩種：1.容量為0，先擴4個sizeof 2.容量占用滿了,擴2個
int newCapacity =php->capacity == 0 ? 4 : php->capacity * 2;
//返回擴容后的內(nèi)存新地址 //擴容后的新大小
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
//擴容后的新地址
php->a = tmp;
//新容量
php->capacity = newCapacity;
}
// php->size下標位置 先將x放最后，后面再調(diào)整
php->a[php->size] = x;
// 有效數(shù)據(jù)++
php->size++;
// 向上調(diào)整 //size-1為新插入數(shù)據(jù)的下標
AdjustUp(php->a, php->size - 1);
}向上調(diào)整（這次用的是小堆）
向上調(diào)整的前提：左右子樹是堆?，時間復雜度O(logN)
//向上調(diào)整 //新插入的數(shù)據(jù)下標
void AdjustUp(HPDataType* a, int child)
{
//定義其父節(jié)點的下標
int parent = (child - 1) / 2;
//循環(huán)
while (child > 0)
{
//如果子小于父就交換 （小堆）
if (a[child] < a[parent])
{
//數(shù)值交換
Swap(&a[child], &a[parent]);
//下標
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}堆的刪除（刪除根）
先判空，看下是否還有元素可以刪除。根數(shù)據(jù)先和最后一個孩子交換位置，孩子再向下調(diào)整。
//刪除
void HeapPop(HP* php)
{
assert(php);
//確保有元素可刪
assert(php->size > 0);
//最后一個孩子和要刪除的根交換
Swap(&php->a[0], &php->a[php->size - 1]);
//有效元素size減減，相當于刪除了交換后的原來的根
--php->size;
//刪除后向下調(diào)整
AdjustDown(php->a, php->size, 0);
}向下調(diào)整（這次用的小堆）
向下調(diào)整的前提：左右子樹是堆?
//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
//n下標位置已經(jīng)沒有數(shù)了
while (child < n)
{
//選小的孩子往上?。ㄐ《眩? if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
//若小的孩子都小于父，則交換
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//交換后下來的數(shù)重新變成parent，繼續(xù)向下調(diào)整
parent = child;
child = parent * 2 + 1;
}
}
}堆排序
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆刪除思想來進行排序
建堆：向上調(diào)整法建堆的時間復雜度：O(N*logN)
? ? ? ? ? ?向下調(diào)整法建堆的時間復雜度：O(N)
可以用堆刪除思想向下調(diào)整法將棧頂和最后一個元素交換，依次將最大的次大的......往后放，就達到了升序排列。
void HeapSort(int* a, int n)
{
//建堆 這里可以選建大堆還是小堆
// 向下調(diào)整建堆
// O(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;
}
}TOP-K問題
TOP-K
問題：即求數(shù)據(jù)結(jié)合中前
K
個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大
。
比如：專業(yè)前
10
名、世界
500
強、富豪榜、游戲中前
100
的活躍玩家等。
對于
Top-K
問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了
(
可能
數(shù)據(jù)都不能一下子全部加載到內(nèi)存中
)
。最佳的方式就是用堆來解決，基本思路如下：
1.
用數(shù)據(jù)集合中前
K
個元素來建堆
前
k
個最大的元素，則建小堆
前
k
個最小的元素，則建大堆
2.
用剩余的
N-K
個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N-K
個元素依次與堆頂元素比完之后，堆中剩余的
K
個元素就是所求的前
K
個最小或者最大的元素
先創(chuàng)建一個包含有10000000個數(shù)的data.txt文本文件。
void CreateNDate()
{
// 造數(shù)據(jù)
int n = 10000000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}前k個建小堆（堆頂元素為k中最?。?，剩余n-k個依次和堆頂元素比較，比k大就插入堆中（插入堆插入向下調(diào)整法），完成后打印前k個元素。
void PrintTopK(const char* filename, int k)
{
// 1. 建堆--用a中前k個元素建堆
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//給堆開辟空間
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
// 前k個數(shù)建小堆
for (int i = (k - 2) / 2; i >= 0; --i)
{
AdjustDown(minheap, k, i);
}
// 2. 將剩余n-k個元素依次與堆頂元素交換，不滿則則替換
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
// 替換你進堆
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
printf("\n");
free(minheap);
fclose(fout);
}
假設k等于5，成功打印出前5個最大的數(shù)據(jù)
文章來源：http://www.zghlxwxcb.cn/news/detail-754375.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-754375.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】堆(Heap):堆的實現(xiàn)、堆排序、TOP-K問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
