堆排序和Topk問題

堆排序

堆排序即利用堆的思想來進行排序,

總共分為兩個步驟:

1. 建堆 升序:建大堆;? ?降序:建小堆

2 .利用堆刪除思想來進行排序

利用堆刪除思想來進行排序 建堆和堆刪除中都用到了向下調整,因此掌握了向下調整,就可以完成堆排序。

建堆

我們建堆的也利用我們的向下調整來建立我們的堆,但是我們不從我們的根開始,因為如果從根開始的話可以用我們的向上調整建堆,但是時間會比我們的向下調整建堆。

我們向下調整的是用是從底下開始,使我們的分支是一個堆,然后在使我們的整體是一個堆。

向下調整來排序

這里的排序和我們的堆的數據的刪除相似。我們將我們的根和數組的最后一個元素進行交換后,我們的count--,在將剩下的元素進行向下調整,那么數組的最后的數字就是我們的最大的數字或者最小的數字。我們進行調整完我們堆 的根就是我們第二小(大)的數字,如此在進行交換和調整這樣我們的數組就會變成有序的(升序或者降序)(我們這里寫的是降序)。

總代碼:

//對數組進行堆排序
void HeapSort(int* a, int n)
{//建堆int i = 0;int count = n;for (i = (n-1-1)/2; i>=0; i--){AdjustDown(a, i, n);}for (i = 0; i < n; i++){Swag(&a[0], &a[n - i - 1]);count--;AdjustDown(a, 0,count );}
}

Topk問題

TOP-K問題:即求數據結合中前K個最大的元素或者最小的元素,一般情況下數據量都比較大。 比如:專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。

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

最佳的方式就是用堆來解決,基本思路如下:

1. 用數據集合中前K個元素來建堆 前k個最大的元素,則建小堆 前k個最小的元素,則建大堆

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

當我們所有的數據比完后,這個堆中就只剩下我們的最大的或者最小的前k個數。這樣需要的空間不會很大。

代碼:

//創建數據,放在文件里面,隨機數。
void CreakData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("FILE* fin eorror");return;}srand((unsigned int)time(0));int i = 0;for (i = 0; i < 100000; i++){int count = rand() % 100000;fprintf(fin, "%d ", count);}fclose(fin);}
//解決topk問題
void  PrintTopK(int k)
{//topK問題int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("malloc");}int i = 0;int count = 0;//創建數據/*CreakData();*///打開文件FILE* fin = fopen("data.txt", "r");if (fin == NULL){perror("fopen!");return;}//讀取前面k個數字for (i = 0; i < k; i++){fscanf(fin, "%d", &topk[i]);}//建堆for (i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, i, k);}//開始往后面讀取數字,如果比我們的堆頂的數字大就和我們堆頂的數字交換//fsanf的返回值是他讀取到字符個數.while (fscanf(fin, "%d", &count) == 1){if (count > topk[0]){//交換并調整,使它形成新的堆topk[0] = count;AdjustDown(topk, 0, k);}}for (i = 0; i < k; i++){printf("%d ", topk[i]);}fclose(fin);free(topk);
}

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

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

相關文章

外賣系統關于redis使用解決高并發情況

1、如何配置redis 在java中操作redis 操作步驟&#xff1a; 1、導入Spring Data Redis的maven坐標 2、配置Redis數據源 3、編寫配置類&#xff0c;創建RedisTemplate對象 4、通過RedisTemplate對象操作Redis 2、Redis結合Lua腳本 減少網絡開銷&#xff1a;使用Lua腳本&#xf…

FolkMQ v1.5.1 發布(“新式”國產消息中間件)

FolkMQ 是個“新式”的消息中間件。強調&#xff1a;“小而巧”、“簡而強”。 功能簡表 角色功能生產者&#xff08;客戶端&#xff09;發布普通消息、Qos0消息、定時消息、順序消息、可過期消息、事務消息、廣播消息消費者&#xff08;客戶端&#xff09;訂閱、取消訂閱。消…

前端面試題日常練-day27 【面試題】

題目 希望這些選擇題能夠幫助您進行前端面試的準備&#xff0c;答案在文末。 1. 在Vue中&#xff0c;以下哪個選項可以用于監聽數據的變化并執行相應的操作&#xff1f; a) computed b) methods c) data d) watch 2. 在Vue中&#xff0c;以下哪種方式可以實現組件之間的通信…

中醫理療元宇宙 科技賦能中醫藥產業走向國際市場

基于380億參數量&#xff0c;對中醫藥海量文本進行數據訓練&#xff0c;實現方劑優化、機制闡釋和新適應癥的精準發現……日前在天津召開的數智賦能大健康產業新質生產力暨第四屆中醫藥國際發展大會上&#xff0c;由天士力醫藥集團與華為云共同開發的“數智本草”中醫藥大模型正…

37. 解數獨 - 力扣(LeetCode)

基礎知識要求&#xff1a; Java&#xff1a; 方法、for循環、if else語句、數組 Python&#xff1a; 方法、for循環、if else語句、列表 題目&#xff1a; 編寫一個程序&#xff0c;通過填充空格來解決數獨問題。 數獨的解法需 遵循如下規則&#xff1a; 數字 1-9 在每一行…

Windows搭建Nginx代理本地盤的文件(共享路徑或本地路徑)

文章目錄 Windows搭建Nginx代理本地盤的文件 - 前言需求背景掛載網絡共享路徑檢查連接狀態下載Nginx編輯 Nginx 配置文件啟動 Nginx檢測Nginx是否成功啟動使用方法遠程共享路徑示例本地文件示例 測試 Windows搭建Nginx代理本地盤的文件 - 前言 在開發過程中&#xff0c;確保文…

ChatGPT Mac客戶端 下載安裝教程(免費 不限次數使用 還支持語音聊天)

ChatGPT Mac客戶端 下載安裝教程&#xff08;免費 不限次數使用 還支持語音聊天&#xff09; 原文鏈接&#xff1a;https://blog.csdn.net/weixin_48311847/article/details/139248625 免費 不限次數使用 還支持語音聊天

mysql 排序、查詢執行流程、幻讀

文章目錄 MySQL的 ORDER BY 執行流程示例表和查詢語句執行流程全字段排序Rowid 排序全字段排序 VS rowid排序聯合索引優化覆蓋索引優化 小結思考題問題執行過程中是否需要排序&#xff1f;如何在數據庫端實現不排序&#xff1f;實現分頁需求 使用ORDER BY RAND()內存臨時表與磁…

ANDROID OLLVM 混淆配置

安裝環境 MacOSGITCMAKENDK - 21.1.6352462 步驟 1. 編譯項目 此項目版本較低 https://github.com/obfuscator-llvm/obfuscator &#xff0c;我們使用 https://github.com/heroims/obfuscator 進行編譯 git clone https://github.com/heroims/obfuscator.gitcd obfuscator…

曼城四連冠,劍南春與萬千球迷共同見證“榮耀時刻”

執筆 | 洪大大 編輯 | 揚 靈 5月19日&#xff0c;英超2023-2024賽季第38輪比賽全面開打&#xff0c;憑借隊員的出色發揮&#xff0c;曼城最終以3-1戰勝西漢姆聯&#xff0c;成功捧起了英超聯賽的獎杯&#xff0c;成為英格蘭足球頂級聯賽100多年歷史上第一支成就四連冠的豪門…

事務報錯沒有顯示回滾導致DDL阻塞引發的問題

在業務開發過程中&#xff0c;顯示的開啟事務并且在事務處理過程中對不同的情況進行顯示的COMMIT或ROLLBACK&#xff0c;這是一個完整數據庫事務處理的閉環過程。 這種在應用開發邏輯層面去handle的事務執行的結果&#xff0c;既確保了事務操作的數據完整性&#xff0c;又遵循了…

簡單句語法

簡單句是指包含一個主語和一個謂語的句子&#xff0c;它表達一個完整的思想。簡單句是構成更復雜句子的基礎。 簡單句的兩種基本結構 簡單句可以分為兩種基本結構&#xff1a; 主謂結構: 描述主語所做的動作或行為&#xff0c;也就是 “做什么”。 主系結構: 描述主語的狀態…

Python2和Python3對utf8的實現方式有什么區別?

# -*- coding: utf8 -*- 是一個特殊的文件頭部注釋&#xff0c;通常出現在Python 2的源代碼文件的開頭。這個注釋告訴Python解釋器&#xff0c;該源文件使用的是UTF-8編碼。這對于包含非ASCII字符&#xff08;例如中文字符、特殊符號等&#xff09;的Python源代碼文件來說非常重…

探索未來設計新境界,PSAI插件 藝術創作神器來襲!

想象一下&#xff0c;如果有一個工具&#xff0c;能夠讓你的設計工作變得既簡單又高效&#xff0c;那會是怎樣的體驗&#xff1f;現在&#xff0c;夢想成真了&#xff01; 這是一款革命性的PSAI設計插件&#xff0c;專為創意人士打造。它將徹底改變你的設計流程&#xff0c;讓你…

【OpenCV】像素信息統計

介紹了計算像素均值、方差的API&#xff0c;以及統計像素信息的方法。相關API&#xff1a; minMaxLoc()mean()meanStdDev() 代碼&#xff1a; #include "iostream" #include "opencv2/opencv.hpp"using namespace std; using namespace cv;int main(int…

談談如何建立可落地的數字化轉型戰略

數字化轉型戰略是指將數字技術集成到企業或組織的所有領域&#xff0c;從根本上改變其運營方式以及為客戶提供價值的方式。它涉及采用新技術并重新思考現有業務流程&#xff0c;以提高效率、生產力和客戶滿意度。 成功的數字化轉型戰略需要采用涉及人員、流程和技術的整體方法。…

【全開源】JAVA同城搬家系統源碼小程序APP源碼

JAVA同城搬家系統源碼 特色功能&#xff1a; 強大的數據處理能力&#xff1a;JAVA提供了豐富的數據結構和算法&#xff0c;以及強大的并發處理能力&#xff0c;使得系統能夠快速地處理大量的貨物信息、司機信息、訂單信息等&#xff0c;滿足大規模物流的需求。智能路徑規劃&a…

香橙派 AIPro開發板上手測評

前言 最近拿到了一個新玩具&#xff1a;香橙派 AIPro。一個只比銀行卡大一點點的開發板能帶給我們多少驚喜呢&#xff1f;接下來就跟我一起來體驗下這塊開發板的魅力。 一、硬件配置 CPU&#xff1a;配備了4核64位ARM處理器&#xff0c;其中默認預留1個給AI處理器使用 NPU&am…

SpringBoot和Apache Doris實現實時廣告推薦系統

本專題旨在向讀者深度解讀Apache Doris技術,探討其與SpringBoot框架結合在各類實際應用場景中的角色與作用。本專題包括十篇文章,每篇文章都概述了一個特定應用領域,如大數據分析、實時報告系統、電商數據分析等,并通過對需求的解析、解決方案的設計、實際應用示例的展示以…

【Python實戰】你還在沖會員看電影電視劇嗎?Python帶你實現各大資源免費看!

前言 halo&#xff0c;包子們下午好 今天給大家實現一個視頻播放器&#xff0c;可以看任何電影&#xff0c;電視劇&#xff0c;不要再為以后看電視看電影而煩惱&#xff0c;今天是福利文章&#xff0c;相信我絕對有用&#xff01; 開發工具 Python版本&#xff1a;3.7.8 相…