數據結構筆記8:堆

目錄

滿二叉樹:??

完全二叉樹:

堆是一種特殊的完全二叉樹:

我們可以以數組的方式存儲堆。

父節點和子節點下標關系的推導:

1.使用數學歸納法證明n2 + 1 = n0:

2.使用邊和節點的關系證明n2 + 1 = n0:

我們來看看堆有哪些方法:

向下調整算法:

向上調整算法:

堆排序:

向下調整建堆:

向上調整建堆:

topk問題:


滿二叉樹:??

定義
一棵深度為?kk?的滿二叉樹,是指所有非葉子節點都有左右子節點,且所有葉子節點都在最底層的二叉樹。換句話說,滿二叉樹的每一層都被完全填滿。

完全二叉樹:

定義:

一棵深度為?kk?的完全二叉樹,除了最后一層外,其他層的節點都被完全填滿,且最后一層的節點盡可能靠左排列。完全二叉樹允許最后一層不滿,但空缺只能出現在右側。

堆是一種特殊的完全二叉樹:

滿足以下性質:

  1. 完全二叉樹結構:堆的邏輯結構是一棵完全二叉樹(所有層除最后一層外都被填滿,且最后一層的節點盡可能靠左排列)。

  2. 堆序性質(Heap Property)

    • 最大堆(Max Heap):每個節點的值 ≥ 其子節點的值(根節點是最大值)。

    • 最小堆(Min Heap):每個節點的值 ≤ 其子節點的值(根節點是最小值)。

當我們給完全二叉樹的每個節點從上到下從左到右編個序號。

我們可以發現父節點和子節點的序號之間存在一些關系。

parent*2 + 1 = childleft(左子節點)

parent*2 + 2 = childright(右子節點)

(child-1)/2 = parent.(這是C語言的計算)

當我們知道父節點的下標,就能知道子節點的下標,知道子節點的下標也可以知道父節點的下標。

我們可以以數組的方式存儲堆。

注意:

1.只有向下取整的計算規則(當x是小數時,取不大于x的最大整數)才能用數組的形式存儲完全二叉樹。

2.只有完全二叉樹適合用數組來存儲

父節點和子節點下標關系的推導:

證明這個關系我們用到了一個二叉樹的結論:n2 + 1= n0:度為2的節點個數比度為0的節點個數少一個。

而這個結論也是可以證明的

1.使用數學歸納法證明n2 + 1 = n0:

由于第一個節點滿足n2+1 = n0;

假設第k個節點也滿足n2+1 = n0;

我們要證明第k+1個節點也滿足n2 +1 = n0;

第k+1個節點有兩種情況:

情況1:它是一個左子節點:那么度為0的父節點就變成了度為1的節點,同時多出一個度為0的子節點。(度為0的節點個數不變)

情況2:它是一個右子節點:那么度為1的父節點就變成了度為2的節點,同時多出一個度為0的子節點(度為0的節點個數和度為2的節點個數同時+1)。

2.使用邊和節點的關系證明n2 + 1 = n0:

像下面這樣一個二叉樹,一共有6條邊,n0+n1+n2-1(除了根節點外的每個節點都貢獻一條邊)

而邊的個數同時也等于n2*2+n1(度為2的節點個數*2 + 度為1的節點個數)

列等式:n0+n1+n2-1 = n2*2+n1

化簡得:n0 = n2+1

知道了堆可以用數組來存儲,

我們來看看堆有哪些方法:

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;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);

初始化和銷毀不用說,其中基本的方法有插入、刪除和取堆頂數據。以及堆的數據個數和堆的判空。

在插入數據或者刪除數據的時候,為了保證數據始終是以堆的形式在存儲,我們引出了向下調整算法和向上調整算法:

向下調整算法:

從一個根開始,父節點和左右子節點中較大的(或者較小的)那個比較,如果父節點小(或者大)就交換,否則就退出循環。

void AdjustDown(HPDataType* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){//建大堆//找出左右孩子中比較大的那個if ((child + 1 < n) && (a[child] < a[child + 1])){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}

向上調整算法:

從一個子節點開始,和它的父節點比較,不符合堆的關系就交換,符合時退出循環。

在實際實現向上調整算法的時候循環判斷很容易寫錯:

如果這里寫成了parent >= 0就會導致程序死循環:當parent = 0時,child更新后為0,parent再更新還是為0.

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//這個判斷條件很容易寫錯{if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

堆排序:

堆排序的思想就是,對一個無序的數組,首先進行建堆(保證堆頂的數據是最大的或者最小的)。把堆頂的數據交換到堆尾,然后向下調整一遍。同時更新堆尾下標。

void HeapSort(int* a, int 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--;}
}

這里的建堆方式有兩種:一種是向上調整建堆,另一種是向下調整建堆。我們可以分析一下這兩種方式的時間復雜度。

完全二叉樹向下調整建堆和向上調整建堆最好情況下,最后一層只有一個節點,最壞情況下最后一層是滿的,由于我們要分析時間復雜度,所以要選擇滿二叉樹來分析。

向下調整建堆:

從下到上,保證調整的時候只有根不是堆的關系。向下調整建堆可以從第一個非葉子節點開始。

向下調整建堆的時間復雜度是O(N)。

向上調整建堆:

從上到下,保證上層是堆的關系。

向上調整建堆的時間復雜度是N*logN

topk問題:

從n個元素中選出最大(最小)的k個元素。

先建堆,選最大元素建小堆(比榜尾大就入榜),選最小元素建大堆(比榜尾小就入榜)。

void CreateNDate()//創建N個數據的方法
{int n = 10000;FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");exit(1);}srand((unsigned int)time(NULL));for (int i = 0; i < n; i++){fprintf(fin, "%d\n", rand() % 100000 + 1);}fclose(fin);
}
void PrintTopK(int k)
{//入榜條件是比榜尾要大,所以要和榜尾比較int* topk = (int *)malloc(sizeof(int) * k);//打開文件讀取數據FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen fail\n");exit(1);}int num = 0;//入k個數據for (int i = 0; i < k; i++){fscanf(fout, "%d", &num);topk[i] = num;}//向下調整建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//循環判斷數據是否入榜while (fscanf(fout, "%d", &num) != EOF){if (num > topk[0]){topk[0] = num;AdjustDown(topk, k, 0);}}fclose(fout);for (int i = 0; i < k; i++){printf("%d ", topk[i]);}
}

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

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

相關文章

3. lvgl 9.3 vscode 模擬環境搭建 lv_port_pc_vscode-release-v9.3

文章目錄1. 資源下載1. 1 lv_port_pc_vscode1.2 cmake 和 mingw 環境搭建1.3 sdl 下載1.4 下載lvgl_v9.32. 環境搭建2.1 拷貝lvgl 源碼到工程2.2 添加SDL2 依賴2.3 執行工程3. 運行示例1. 資源下載 1. 1 lv_port_pc_vscode 那么多模擬器&#xff0c;為什么選擇這個&#xff1…

【牛客刷題】小紅的爆炸串(二)

一、題目介紹 本題鏈接為:小紅的爆炸串(二) 小紅定義一個字符串會爆炸,當且僅當至少有k對相鄰的字母不同。 例如,當 k k k=2時,"arc"會爆炸,而"aabb"則不會爆炸。 小紅拿到了一個長度為

【實戰】如何訓練一個客服語音對話場景VAD模型

1. 引言:客服場景下的VAD模型 在客服中心,每天都會產生海量的通話錄音。對這些錄音進行有效分析,可以用于服務質量監控、客戶意圖洞察、流程優化等。VAD在其中扮演著“預處理器”和“過濾器”的關鍵角色: 提升ASR效率與準確性:只將檢測到的語音片段送入ASR引擎,可以避免…

在 Dokploy 中為 PostgreSQL 搭建 PgBouncer 數據庫連接池(圖文)

前言&#xff1a;為什么你需要一個連接池&#xff1f; 如果你正在使用 Node.js (尤其是像 Next.js 這樣的框架) 配合 Prisma 操作 PostgreSQL 數據庫&#xff0c;你很可能在某個階段會遇到那個令人頭疼的錯誤&#xff1a;“Error: Too many clients already”。這通常發生在應…

Mac獲取終端歷史

在 macOS 中&#xff0c;歷史記錄文件的位置取決于你使用的 shell。以下是針對不同 shell 的歷史記錄文件的默認位置&#xff1a;對于 Bash 用戶&#xff1a; 歷史記錄文件通常位于 ~/.bash_history。對于 Zsh 用戶&#xff08;macOS Catalina及以后版本默認使用的shell&#x…

高頻交易服務器篇

在 Binance 進行高頻交易&#xff08;HFT&#xff09;時&#xff0c;服務器的低延遲、高穩定性和快速網絡是關鍵。亞馬遜云&#xff08;AWS&#xff09; 提供了多種適合高頻交易的方案&#xff0c;以下是推薦的配置和優化策略&#xff1a;1. 選擇 AWS 區域&#xff08;Region&a…

MVC與MVVM架構模式詳解:原理、區別與JavaScript實現

Hi&#xff0c;我是布蘭妮甜 &#xff01;在當今復雜的前端開發領域&#xff0c;如何組織代碼結構一直是開發者面臨的核心挑戰。MVC和MVVM作為兩種經典的架構模式&#xff0c;為前端應用提供了清晰的責任劃分和可維護的代碼組織方案。本文將深入探討這兩種模式的原理、實現差異…

從小白到進階:解鎖linux與c語言高級編程知識點嵌入式開發的任督二脈(2)

【硬核揭秘】Linux與C高級編程&#xff1a;從入門到精通&#xff0c;你的全棧之路&#xff01; 第三部分&#xff1a;Shell腳本編程——自動化你的Linux世界&#xff0c;讓效率飛起來&#xff01; 嘿&#xff0c;各位C語言的“卷王”們&#xff01; 在Linux的世界里&#xf…

鎖和事務的關系

事務的4大特性(ACID) 原子性&#xff08;Atomicity&#xff09;&#xff1a;事務被視為一個單一的、不可分割的工作單元一致性&#xff08;Consistency&#xff09;&#xff1a;事務執行前后&#xff0c;數據庫從一個一致狀態轉變為另一個一致狀態&#xff0c;并且強制執行所有…

電動車信用免押小程序免押租賃小程序php方案

電動車信用免押租賃小程序&#xff0c;免押租小程序&#xff0c;信用免押接口申請、對接開發&#xff0c;可源碼搭建&#xff0c;可二開或定制。開發語言后端php&#xff0c;前端uniapp。可二開定制 在線選擇門店&#xff0c;選擇車輛類型&#xff0c;選擇租賃方式&#xff08…

機器學習在智能安防中的應用:視頻監控與異常行為檢測

隨著人工智能技術的飛速發展&#xff0c;智能安防領域正經歷著一場深刻的變革。智能安防通過整合先進的信息技術&#xff0c;如物聯網&#xff08;IoT&#xff09;、大數據和機器學習&#xff0c;能夠實現從傳統的被動防御到主動預防的轉變。機器學習技術在智能安防中的應用尤為…

MySQL中DROP、DELETE與TRUNCATE的深度解析

在MySQL數據庫操作中&#xff0c;DROP、DELETE和TRUNCATE是三個常用的數據操作命令&#xff0c;它們都可以用于刪除數據&#xff0c;但在功能、執行效率、事務處理以及對表結構的影響等方面存在顯著差異。本文將從多個維度對這三個命令進行詳細對比和解析&#xff0c;幫助讀者更…

一條 SQL 語句的內部執行流程詳解(MySQL為例)

當執行如下 SQL&#xff1a; SELECT * FROM users WHERE id 1;在數據庫內部&#xff0c;其實會經歷多個復雜且有序的階段。以下是 MySQL&#xff08;InnoDB 引擎&#xff09;中 SQL 查詢語句從發送到結果返回的完整執行流程。 客戶端連接階段 客戶端&#xff08;如 JDBC、My…

超詳細yolo8/11-detect目標檢測全流程概述:配置環境、數據標注、訓練、驗證/預測、onnx部署(c++/python)詳解

文章目錄 一、配置環境二、數據標注三、模型訓練四、驗證預測五、onnx部署c 版python版本 一、配置環境 我的都是在Linux系統下&#xff0c;訓練部署的&#xff1b;模型訓練之前&#xff0c;需要配置好環境&#xff0c;Anaconda、顯卡驅動、cuda、cudnn、pytorch等&#xff1b…

阿里云Flink:開啟大數據實時處理新時代

走進阿里云 Flink 在大數據處理的廣袤領域中&#xff0c;阿里云 Flink 猶如一顆璀璨的明星&#xff0c;占據著舉足輕重的地位。隨著數據量呈指數級增長&#xff0c;企業對數據處理的實時性、高效性和準確性提出了前所未有的挑戰 。傳統的數據處理方式逐漸難以滿足這些嚴苛的需…

【Linux】基礎開發工具(1)

1. 軟件包管理器 1.1 什么是軟件包 在Linux下安裝軟件, ?個常用的辦法是下載到程序的源代碼, 并進行編譯, 得到可執行程序. 但是這樣太麻煩了, 于是有些人把?些常?的軟件提前編譯好, 做成軟件包(可以理解成windows上 的安裝程序)放在?個服務器上, 通過包管理器可以很?便…

藍橋杯51單片機設計

#超聲波原理# ①超聲波測距原理&#xff1a;聲波反射原理 聲波分類&#xff1a; 超聲波測距原理 超聲波頻率越高&#xff0c;波長越短&#xff0c;反身性越強&#xff0c;衍射性越弱 ②超聲波模塊原理 發射原理 跳線帽 接收原理 問題&#xff1a; &#xff11;.超聲波發射模塊需…

【LeetCode 熱題 100】240. 搜索二維矩陣 II——排除法

Problem: 240. 搜索二維矩陣 II 編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性&#xff1a; 每行的元素從左到右升序排列。 每列的元素從上到下升序排列。 文章目錄 整體思路完整代碼時空復雜度時間復雜度&#xff1a;O(M N)空間復…

Android Input 系列專題【inputflinger事件的讀取與分發】

Android輸入系統在native中的核心工作就是&#xff0c;從Linux驅動設備節點中讀取事件&#xff0c;然后將這個事件進行分發&#xff0c;這兩項工作分別交給了InputReader和InputDispatcher來做。 他們的源碼都屬于native層inputflinger里面的一部分&#xff0c;如下架構&#…

【大模型LLM】GPU計算效率評估指標與優化方法:吞吐率

GPU計算效率評估指標與優化方法&#xff1a;吞吐率 一、核心效率指標二、大模型吞吐率&#xff08;Large Model Throughput&#xff09;三、關鍵性能瓶頸分析四、實際測量工具五、優化策略總結 一、核心效率指標 吞吐率&#xff08;Throughput&#xff09; 定義&#xff1a;單位…