數(shù)據(jù)結(jié)構(gòu)之堆的具體使用
更新時(shí)間：2022年02月24日 09:51:50 作者：小倪同學(xué) -_-
本文主要介紹了數(shù)據(jù)結(jié)構(gòu)之堆的具體使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
堆的概念及結(jié)構(gòu)
定義堆
實(shí)現(xiàn)堆的功能首先要定義堆的結(jié)構(gòu)體
typedef int HPDataTpye;
typedef struct Heap
{
HPDataTpye* a; //存儲(chǔ)數(shù)據(jù)
int size; //保存元素個(gè)數(shù)
int capacity; //存儲(chǔ)容量
}HP;
堆的初始化
思路：
- 先開(kāi)辟一塊空間，將傳入的數(shù)據(jù)存放到堆的結(jié)構(gòu)體中
- 將堆中數(shù)據(jù)建堆排序
- 將堆結(jié)構(gòu)中容量，元素個(gè)數(shù)初始化
開(kāi)辟空間不難，那么如何建堆呢？
這里有兩種思路，一是從上往下調(diào)整，二是從下往上調(diào)整
思路一：
從上往下調(diào)整
將傳入的結(jié)點(diǎn)當(dāng)做父節(jié)點(diǎn)，比較其兩個(gè)子節(jié)點(diǎn)，將子節(jié)點(diǎn)與父節(jié)點(diǎn)比較，如果不滿(mǎn)足堆的條件就交換，并將原先子節(jié)點(diǎn)的位置當(dāng)成父節(jié)點(diǎn)，重復(fù)上述操作。如果滿(mǎn)足堆的條件就結(jié)束操作。（注意：該程序是建立在左右子樹(shù)都為大堆基礎(chǔ)上的）
代碼如下
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
// 條件：左右子樹(shù)都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小 or 大的那個(gè)
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續(xù)往下調(diào)整
// 2、如果小 or 大 的孩子比父親大 or 小，則結(jié)束調(diào)整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
思路二：
從下往上建
將傳入的結(jié)點(diǎn)當(dāng)做子節(jié)點(diǎn)，找到其父結(jié)點(diǎn)并與之比較，不滿(mǎn)足堆的條件就交換，并將原父結(jié)點(diǎn)的位置當(dāng)成子節(jié)點(diǎn)重復(fù)之前操作。滿(mǎn)足堆的條件則退出程序。（注意：該程序建立在除傳入的子節(jié)點(diǎn)外，其余結(jié)點(diǎn)都滿(mǎn)足堆條件基礎(chǔ)上的）
代碼實(shí)現(xiàn)
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 不對(duì)的 parent不會(huì)小于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
初始化總體代碼
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
// 條件：左右子樹(shù)都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小 or 大的那個(gè)
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續(xù)往下調(diào)整
// 2、如果小 or 大 的孩子比父親大 or 小，則結(jié)束調(diào)整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 不對(duì)的 parent不會(huì)小于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapInit(HP* php, HPDataTpye* a, int n)
{
assert(php);
//開(kāi)辟空間
php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//轉(zhuǎn)移數(shù)據(jù)
memcpy(php->a, a, sizeof(HPDataTpye)*n);
//建堆排序
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(php->a, n, i);
}
php->capacity = n;
php->size = n;
}
插入數(shù)據(jù)
思路：
- 檢查是否滿(mǎn)容量，滿(mǎn)了就擴(kuò)容
- 插入數(shù)據(jù)，并將size+1
代碼：
void HeapPush(HP* php, HPDataTpye x)
{
assert(php);
if (php->capacity == php->size)
{
HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
if (php->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
判空
思路：
判空只需判斷其元素個(gè)數(shù)是否為0即可
代碼：
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
刪除堆頂?shù)臄?shù)據(jù)
思路：
- 先判空處理
- 將堆頂數(shù)據(jù)和最后一個(gè)葉結(jié)點(diǎn)數(shù)據(jù)交換
- 從上往下調(diào)整堆
代碼：
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
//交換頭尾數(shù)據(jù)
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
獲取堆頂數(shù)據(jù)
思路：
先判空，再取出堆頂數(shù)據(jù)
代碼：
HPDataTpye HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
獲取元素個(gè)數(shù)
直接返回size
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
打印
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
銷(xiāo)毀堆
將開(kāi)辟的空間釋放，并將size,capacity賦值為0
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
Topk問(wèn)題
問(wèn)：如何取出一組數(shù)據(jù)中最大的前K個(gè)值
有人會(huì)想到把所有數(shù)據(jù)建大堆，取出堆頂數(shù)據(jù)再刪除該數(shù)據(jù)，重復(fù)操作K次
操作如下
void TestHeap()
{
int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
HP hp;
HeapInit(&hp, a, sizeof(a) / sizeof(int));
HeapPrint(&hp);
printf("\n");
int k = 0;
scanf("%d", &k);
printf("找出數(shù)組中最小的前%d個(gè)：", k);
while (!HeapEmpty(&hp)&&k--)
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
}
如果該組數(shù)據(jù)個(gè)數(shù)為一萬(wàn)，十萬(wàn)呢？
這時(shí)用該方法不但耗費(fèi)時(shí)間而且十分耗內(nèi)存，那有沒(méi)有時(shí)間復(fù)雜符度較小的用堆實(shí)現(xiàn)的方法呢？
答案是有的，那就是Topk算法
Topk基本思路如下：
用數(shù)據(jù)集合中前K個(gè)元素來(lái)建堆
求前k個(gè)最大的元素，則建小堆
求前k個(gè)最小的元素，則建大堆用剩余的N-K個(gè)元素依次與堆頂元素來(lái)比較，不滿(mǎn)足則替換堆頂元素
將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。
代碼實(shí)現(xiàn)
void PrintTopK(int* a, int n, int k)
{
HP hp;
HeapInit(&hp, a, k);
for(int i = k; i < n; i++)
{
if (a[i]>HeapTop(&hp))
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
檢測(cè)
這里利用隨機(jī)數(shù)來(lái)檢測(cè)
void TestTopk()
{
int n = 100000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
運(yùn)行結(jié)果
代碼總結(jié)
Heap.h 頭文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include<time.h>
typedef int HPDataTpye;
typedef struct Heap
{
HPDataTpye* a;
int size;
int capacity;
}HP;
void Swap(int* px, int* py);
void AdjustDown(int* a, int n, int parent);
void AdjustUp(int* a, int child);
//void HeapInit(HP* php);
//初始化
void HeapInit(HP* php, HPDataTpye* a, int n);
// 插入x，保持他繼續(xù)是堆
void HeapPush(HP* php, HPDataTpye x);
//判空
bool HeapEmpty(HP* php);
// 刪除堆頂數(shù)據(jù)，刪除后保持他繼續(xù)是堆
void HeapPop(HP* php);
// 獲取堆頂?shù)臄?shù)據(jù)，也就是最值
HPDataTpye HeapTop(HP* php);
//獲取堆中元素個(gè)數(shù)
int HeapSize(HP* php);
//打印
void HeapPrint(HP* php);
//銷(xiāo)毀堆
void HeapDestroy(HP* php);
Heap.c 函數(shù)文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
// 條件：左右子樹(shù)都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 選出左右孩子中小 or 大的那個(gè)
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續(xù)往下調(diào)整
// 2、如果小 or 大 的孩子比父親大 or 小，則結(jié)束調(diào)整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 不對(duì)的 parent不會(huì)小于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapInit(HP* php, HPDataTpye* a, int n)
{
assert(php);
//開(kāi)辟空間
php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//轉(zhuǎn)移數(shù)據(jù)
memcpy(php->a, a, sizeof(HPDataTpye)*n);
//建堆排序
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(php->a, n, i);
}
php->capacity = n;
php->size = n;
}
// 插入x，保持它繼續(xù)是堆
void HeapPush(HP* php, HPDataTpye x)
{
assert(php);
if (php->capacity == php->size)
{
HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
if (php->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
// 刪除堆頂數(shù)據(jù)，刪除后保持他繼續(xù)是堆
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
// 獲取堆頂?shù)臄?shù)據(jù)，也就是最值
HPDataTpye HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
void HeapPrint(HP* php)
{
for (int 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->capacity = php->size = 0;
}
test.c 測(cè)試文件
#include "Heap.h"
void TestHeap()
{
int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
HP hp;
HeapInit(&hp, a, sizeof(a) / sizeof(int));
HeapPrint(&hp);
printf("\n");
int k = 0;
scanf("%d", &k);
printf("找出數(shù)組中最小的前%d個(gè)：", k);
while (!HeapEmpty(&hp)&&k--)
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
}
void PrintTopK(int* a, int n, int k)
{
HP hp;
HeapInit(&hp, a, k);
for(int i = k; i < n; i++)
{
if (a[i]>HeapTop(&hp))
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
void TestTopk()
{
int n = 100000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
int main()
{
//TestHeap();
TestTopk();
return 0;
}
到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)之堆的具體使用的文章就介紹到這了,更多相關(guān)數(shù)據(jù)結(jié)構(gòu) 堆內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C/C++通過(guò)IP獲取局域網(wǎng)網(wǎng)卡MAC地址
這篇文章主要為大家詳細(xì)介紹了C++如何通過(guò)Win32API函數(shù)SendARP從IP地址獲取局域網(wǎng)內(nèi)網(wǎng)卡的MAC地址,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-02-02
C 語(yǔ)言基礎(chǔ)之C語(yǔ)言的常見(jiàn)關(guān)鍵字
C語(yǔ)言中有一些預(yù)先定義的字符串，他們本身被賦予了自身的功能。并且我們?cè)诙x變量的時(shí)候，不能去搶他們的名字來(lái)用。他們就是今天的主角：關(guān)鍵字，下面文章將給大家做詳細(xì)介紹2021-09-09
這篇文章主要介紹了C語(yǔ)言中的多行輸入問(wèn)題及說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
C語(yǔ)言中static與extern關(guān)鍵字的深入解析
在C語(yǔ)言編程中,static和extern是兩個(gè)非常重要的關(guān)鍵字,它們各自有著獨(dú)特的用途,本文將深入探討這兩個(gè)關(guān)鍵字的工作原理、底層實(shí)現(xiàn)機(jī)制以及在實(shí)際開(kāi)發(fā)中的應(yīng)用,感興趣的小伙伴跟著小編一起來(lái)學(xué)習(xí)學(xué)習(xí)吧2024-09-09
C++實(shí)現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹(shù))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹(shù)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單推箱子小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)推箱子小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-11-11
這篇文章主要介紹了C語(yǔ)言 掃雷程序的實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2017-03-03
opencv3/C++實(shí)現(xiàn)霍夫圓/直線(xiàn)檢測(cè)
今天小編就為大家分享一篇opencv3/C++實(shí)現(xiàn)霍夫圓/直線(xiàn)檢測(cè)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12
這篇文章主要介紹了C語(yǔ)言 聯(lián)合(union)用法案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了一文詳解C++的程序流程控制，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-08-08