數據結構--堆的實現

目錄

一、堆的概念及結構

二、小根堆的實現

2.1 堆的數據結構

2.2 堆的初始化HeapInit

2.3 堆的銷毀HeapDestory

2.4 堆的插入HeapPush

?2.4.1 插入代碼HeapPush

2.4.2 向上調整代碼AdjustUp

2.4.3 交換數據代碼Swap

2.5 堆的刪除HeapPop

2.5.1 刪除代碼HeapPop

2.5.2 向下調整算法AdjustDown

2.6?取堆頂的數據HeapTop

2.7?獲取堆的數據個數HeapSize

2.8?堆的判空HeapEmpty

三、堆的應用

3.1 堆排序

3.2 TOP-K問題

3.2.1 創建大量數據

3.2.2 求K個最大的元素

3.2.3 驗證

四、代碼

4.1 堆的代碼

4.1.1 Heap.h

4.1.2 Heap.c

4.2 堆排序的代碼

4.3 TOP-K的代碼


一、堆的概念及結構

堆(Heap)是一種特殊的數據結構,通常以完全二叉樹的形式呈現。

堆的核心特性是:

  • 對于大根堆,任意父節點的值都大于或等于其子節點的值
  • 對于小根堆,任意父節點的值都小于或等于其子節點的值

堆通常使用數組來模擬完全二叉樹的結構。數組索引按照從上到下、從左到右的方式對應樹的節點排列。假設某個節點在數組中的位置為i,則其左子節點和右子節點的位置分別為 2*i+1 2*i+2,而其父節點的位置為(i-1)/2

如下所示:

二、小根堆的實現

2.1 堆的數據結構

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

2.2 堆的初始化HeapInit

void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}

2.3 堆的銷毀HeapDestory

// 堆的銷毀
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}

2.4 堆的插入HeapPush

假如,我們現在有一個數組a:15 18 19 25 28 34 65 49 27 37,他從邏輯上看,是一個小根堆結構,我們將它的邏輯結構畫出來如下所示:

我們現在想要將10插入堆里面去,插入10之后,要不允許破壞原本小根堆的結構,所以我們就需要將10一步一步的調整,如下所示:

2.4.1 插入代碼HeapPush

// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4.2 向上調整代碼AdjustUp

//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}

2.4.3 交換數據代碼Swap

//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}

2.5 堆的刪除HeapPop

堆的刪除,我們首先要確定刪除哪一個元素,看上面的數組a:10 15 19 25 18 34 65 49 27 37 28.我們畫出他的二叉樹表現形式,如下所示,他滿足小根堆特性。

?現在數組中有這么多的元素,我們要刪除哪一個呢?最常見的是刪除第一個元素和最后一個元素,如果我們刪除最后一個元素28,刪除的沒有意義,他既不是最大的也不是最小的,所以堆的刪除一般都是刪除堆頂元素,也就是以一個元素,刪除堆頂元素之后,后面的元素需要向前移動嗎?答案是不能,如果向前移動,元素之間的邏輯關系會改變,不滿足小堆特性,所有如果我們要刪除第一個元素,通常做法是將最后一個元素與第一個元素互換,只有第一個元素不滿足小根堆的特性,其他元素都滿足,我們還需要寫一個向下調整算法。

2.5.1 刪除代碼HeapPop

// 堆的刪除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}

2.5.2 向下調整算法AdjustDown

void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}

2.6?取堆頂的數據HeapTop

// 取堆頂的數據
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}

2.7?獲取堆的數據個數HeapSize

// 堆的數據個數
int HeapSize(Heap* php) {assert(php);return php->size;
}

2.8?堆的判空HeapEmpty

// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

三、堆的應用

3.1 堆排序

如果我們想要升序的話,就需要建立大根堆。

如果我們想要降序的話,就需要建立小根堆。

現在我們有一個數組a{ 27,15,19,18,28,34,65,49,25,37 };我們想要將a進行從小到大排序,所以我們就需要對這個數組進行建堆處理。

那現在我們如何建堆呢?

方法一:我們可以訪問數組的每一個元素,然后初始化一個堆,將數組的每一個元素插入到堆里面,我們根據堆的自動調整算法,可以自動的變成大根堆,然后我們取出堆頂的元素,把它放在數組里面,然后堆的刪除,重復n次。但是這樣空間復雜度太高了需要重新新建一個堆。

方法二:我們可以從數組的第二個元素開始,進行向上調整算法,就這個數組變成一個堆,如下所示:

for (int i = 1; i < size; i++) {AdjustUp(a, i);
}

我們打開我們的調試,看到數組a成功的變成了一個大根堆。但是這樣時間復雜度太高了。

方法三:可以從最后一個分支節點開始,依次進行向下調整算法,如下所示:

for (int i =(size-2)/2 ; i >= 0; i--)//
{AdjustDown(a, i, size);
}

我們常用的建堆算法是方法三。?

建完堆之后,我們將堆頂元素與最后一個元素互換,然后重新調整堆,重復n次。代碼如下所示:

int end = size - 1;
while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;
}

這樣我們就成功的將數組a從小到大排序了。

3.2 TOP-K問題

TOP-K問題:即求數據結合中前K個最大的元素或者最小的元素,一般情況下數據量都比較大

比如:專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。

對于Top-K問題,能想到的最簡單直接的方式就是排序,但是:如果數據量非常大,排序就不太可取了(可能數據都不能一下子全部加載到內存中)。最佳的方式就是用堆來解決,基本思路如下:

1. 用數據集合中前K個元素來建堆

????????前k個最大的元素,則建小堆

????????前k個最小的元素,則建大堆

2. 用剩余的N-K個元素依次與堆頂元素來比較,不滿足則替換堆頂元素

????????將剩余N-K個元素依次與堆頂元素比完之后,堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

3.2.1 創建大量數據

我們使用代碼創建大量的數據,如下所示:

void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = rand()+i;fprintf(pf, "%d\n", number);}
}

3.2.2 K個最大的元素

首先,輸入k的值,malloc出k個int類型的空間,然后從文件中讀取前k個數,將他們放在malloc出來的空間里面,將他們建成小堆,最后依次讀取文件中后n-k個,依次與堆頂進行比較,如果大于堆頂就替換,然后調整堆。代碼如下:

void TOP_K() {printf("請輸入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//從文件中拷貝k個數到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k個數的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//讀取剩下的n-k個數據int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d個數", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}

3.2.3 驗證

我們現在已經把最大的前k個輸出了,我們如何驗證這k個元素就是十萬個數據中最大的前10個呢?

我們在創建數據的時候可以%10000000,來控制我們的數據,創建完成數據之后,我們在data.txt文檔中隨機的修改k個數,在它們后面加上4個0,這樣我們就知道k個最大的數后面肯定有4個0。我們調用top-k函數,如下所示:

可以看到最大的10個數后面都帶有4個0,說明我們所寫的top-k算法沒有問題。

四、代碼

4.1 堆的代碼

4.1.1 Heap.h

#pragma once
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
void AdjustDown(HPDataType* a, int parent, int size);
void AdjustUp(HPDataType* a, int child);
//交換函數
void Swap(HPDataType* x, HPDataType* y);
void HeapInit(Heap* php);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂的數據
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

4.1.2 Heap.c

#include"Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}
// 堆的銷毀
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}
//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
// 堆的刪除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
// 取堆頂的數據
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}
// 堆的數據個數
int HeapSize(Heap* php) {assert(php);return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

4.2 堆排序的代碼

//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void HeapSort(int* a, int size) {for (int i =(size-2)/2 ; i >= 0; i--)//{AdjustDown(a, i, size);}int end = size - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}
int main() {int a[] = { 27,15,19,18,28,34,65,49,25,37 };int size = sizeof(a) / sizeof(a[1]);HeapSort(a, size);for (int i  = 0; i < size; i++) {printf("%d ", a[i]);}return 0;
}

4.3 TOP-K的代碼

//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = (rand()+i)%10000000;fprintf(pf, "%d\n", number);}
}
void TOP_K() {printf("請輸入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//從文件中拷貝k個數到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k個數的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//讀取剩下的n-k個數據int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d個數", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
int main() {srand((unsigned int)time(NULL));CreatData();TOP_K();return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/88299.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/88299.shtml
英文地址,請注明出處:http://en.pswp.cn/web/88299.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

evo軌跡評估工具

文章目錄evo參數設置evo_traj指標度量evo_apeevo_rpe結果比較evo工具主要有如下六個常用命令&#xff1a; evo_ape - 用于評估絕對位姿誤差&#xff1b;evo_rpe- 用于評估相對位姿誤差&#xff1b;evo_traj - 這個主要是用來畫軌跡、輸出軌跡文件、轉換數據格式等功能&#xf…

Django+DRF 實戰:自定義異常處理流程

文章目錄一、DRF 異常處理流程DRF 默認異常處理流程源碼二、實戰DRF 自定義異常處理流程應用自定義異常處理流程一、DRF 異常處理流程 DRF 默認異常處理流程 DRF默認的異常處理流程如下&#xff1a; 當異常發生時&#xff0c;會自動調用rest_framework.views.exception_hand…

Spring MVC 1

什么是Spring Web MVC 官方對Spring MVC的描述是這樣的&#xff1a;Spring Web MVC 是基于Severlet API構建的原始Web框架&#xff0c;從一開始就包含在Spring框架中。它的正式名稱“Spring Web MVC”來自其源模塊的名稱&#xff08;Spring-webmvc&#xff09;&#xff0c;但它…

一個基于若依(ruoyi-vue3)的小項目部署記錄

一、背景 收到朋友的求助&#xff0c;他拿到了一個項目的源代碼&#xff0c;說需要我幫助部署。部署要求是需要域名訪問。 因為沒有文檔和其他資料以及幫助&#xff0c;我先清理了源收到的資料&#xff1a; 1.后端&#xff1a;是java代碼&#xff0c;一看就是若依框架。心里大大…

【實戰總結】WMIC在HW行動中的4類關鍵應用

WMIC命令完全指南&#xff1a;網絡安全運維工程師的深度實踐手冊 關鍵詞&#xff1a;WMIC命令、Windows管理、網絡安全運維、系統信息收集、進程分析、自動化審計 【實戰總結】WMIC在HW行動中的4類關鍵應用 1. 前言 在Windows環境下的網絡安全運維中&#xff0c;WMIC&#x…

LKT4304穩定可靠高兼容性國產安全加密芯片

隨著 IOT 的飛速發展&#xff0c;智能家居&#xff0c;智能汽車&#xff0c;智能工控等物聯網設備和云服務的安全問題成為IOT普及的關鍵障礙。在設計之初就為物聯網產品配備正確的安全解決方案&#xff0c;是幫助預防措施的關鍵所在。LKT4304是凌科芯安專為物聯網應用場景而推出…

Android 網絡開發核心知識點

Android 網絡開發核心知識點 一、基礎網絡通信 1. HTTP/HTTPS 協議 HTTP方法&#xff1a;GET、POST、PUT、DELETE等狀態碼&#xff1a;200(成功)、404(未找到)、500(服務器錯誤)等HTTPS加密&#xff1a;SSL/TLS握手過程報文結構&#xff1a;請求頭/響應頭、請求體/響應體 2. 網…

DVWA靶場通關筆記-弱會話IDs(Weak Session IDs Medium級別)

目錄 一、Session ID 二、代碼審計&#xff08;Medium級別&#xff09; 1、配置security為Medium級別 2、源碼分析 &#xff08;1&#xff09;index.php &#xff08;2&#xff09;Medium.php &#xff08;3&#xff09;對比分析 &#xff08;4&#xff09;滲透思路 三…

編輯器Vim的快速入門

如大家所了解的&#xff0c;Vim是一個很古老的編輯器&#xff0c;但是并沒有隨著時間的流逝消失在編輯器/IDE 的競爭中&#xff0c;Vim 獨創的模式機制和 hjkl 移動光標方式使得使用者在編輯文件時可以雙手不離開鍵盤&#xff0c;極大地提升了工作效率。由于 Vim 學習曲線極為陡…

深度學習核心:從基礎到前沿的全面解析

&#x1f9e0; 深度學習核心&#xff1a;從基礎到前沿的全面解析 &#x1f680; 探索深度學習的核心技術棧&#xff0c;從神經網絡基礎到最新的Transformer架構 &#x1f4cb; 目錄 &#x1f52c; 神經網絡基礎&#xff1a;從感知機到多層網絡&#x1f5bc;? 卷積神經網絡&am…

MySQL索引:數據庫的超級目錄

MySQL索引&#xff1a;數據庫的「超級目錄」 想象你有一本1000頁的百科全書&#xff0c;要快速找到某個知識點&#xff08;如“光合作用”&#xff09;&#xff1a; ? 無索引&#xff1a;逐頁翻找 → 全表掃描&#xff08;慢&#xff01;&#xff09;? 有索引&#xff1a;直接…

景觀橋 涵洞 城門等遮擋物對汽車安全性的影響數學建模和計算方法,需要收集那些數據

對高速公路景觀橋影響行車視距的安全問題進行數學建模&#xff0c;需要將物理幾何、動力學、概率統計和交通流理論結合起來。以下是分步驟的建模思路和關鍵模型&#xff1a;一、 核心建模目標 量化視距&#xff08;Sight Distance, SD&#xff09;&#xff1a;計算實際可用視距…

Git 用戶名和郵箱配置指南:全局與項目級設置

查看全局配置 git config --global user.name # 查看全局name配置 git config --global user.email # 查看全局email配置 git config --global --list # 查看所有全局配置查看當前項目配置 git config user.name # 查看當前項目name配置 git config user.email # 查看當前項目…

視頻序列和射頻信號多模態融合算法Fusion-Vital解讀

視頻序列和射頻信號多模態融合算法Fusion-Vital解讀概述模型整體流程視頻幀時間差分歸一化TSM模塊視頻序列特征融合模塊跨模態特征融合模塊概述 最近看了Fusion-Vital的視頻-射頻&#xff08;RGB-RF&#xff09;融合Transformer模型。記錄一下&#xff0c;對于實際項目中的多模…

frp內網穿透下創建FTP(解決FTP“服務器回應不可路由的地址。使用服務器地址替代”錯誤)

使用寶塔面板&#xff0c;點擊FTP&#xff0c;下載Pure-FTPd插件 點擊Pure-FTPd插件&#xff0c;修改配置文件&#xff0c;找到PassivePortRange, 修改ftp被動端口范圍為39000 39003&#xff0c;我們只需要4個被動端口即可&#xff0c;多了不好在內網穿透frp的配置文件中增加…

STM32控制四自由度機械臂(SG90舵機)(硬件篇)(簡單易復刻)

1.前期硬件準備 2s鋰電池一個&#xff08;用于供電&#xff09;&#xff0c;stm32f103c8t6最小系統板一個&#xff08;主控板&#xff09;&#xff0c;兩個搖桿&#xff08;用于搖桿模式&#xff09;&#xff0c;四個電位器&#xff08;用于示教器模式&#xff09;&#xff0c…

華為OD機試_2025 B卷_最差產品獎(Python,100分)(附詳細解題思路)

題目描述 A公司準備對他下面的N個產品評選最差獎&#xff0c; 評選的方式是首先對每個產品進行評分&#xff0c;然后根據評分區間計算相鄰幾個產品中最差的產品。 評選的標準是依次找到從當前產品開始前M個產品中最差的產品&#xff0c;請給出最差產品的評分序列。 輸入描述 第…

飛算JavaAI:重塑Java開發效率的智能引擎

飛算JavaAI:重塑Java開發效率的智能引擎 一、飛算JavaAI核心價值 飛算JavaAI是全球首款專注Java語言的智能開發助手,由飛算數智科技(深圳)有限公司研發。它通過AI大模型技術實現: 全流程自動化:從需求分析→軟件設計→代碼生成一氣呵成工程級代碼輸出:生成包含配置類、…

Java和Go各方面對比:現代編程語言的深度分析

Java和Go各方面對比&#xff1a;現代編程語言的深度分析 引言 在當今的軟件開發領域&#xff0c;選擇合適的編程語言對項目的成功至關重要。Java作為一門成熟的面向對象語言&#xff0c;已經在企業級開發中占據主導地位超過25年。而Go&#xff08;Golang&#xff09;作為Google…

CloudCanal:一款企業級實時數據同步、遷移工具

CloudCanal 是一款可視化的數據同步、遷移工具&#xff0c;可以幫助企業構建高質量數據管道&#xff0c;具備實時高效、精確互聯、穩定可拓展、一站式、混合部署、復雜數據轉換等優點。 應用場景 CloudCanal 可以幫助企業實現以下數據應用場景&#xff1a; 數據同步&#xff…