《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭(zhēng) 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第6章 堆

一、堆：如何維護(hù)動(dòng)態(tài)集合的最值

這一部分介紹了

• 堆的定義

• 堆的存儲(chǔ)

• 往堆中插入元素

• 刪除堆頂元素

• 刪除任意元素

• 堆的性能分析

這一部分，涉及堆的基礎(chǔ)內(nèi)容，各種教材都有。作者為了體現(xiàn)特色，在本節(jié)加入了一個(gè)引導(dǎo)式問(wèn)題：假設(shè)有一個(gè)動(dòng)態(tài)數(shù)據(jù)集合，針對(duì)該集合，有4種操作：插入數(shù)據(jù)、按值刪除數(shù)據(jù)、查詢最大值和刪除最大值。如何實(shí)現(xiàn)這樣一個(gè)動(dòng)態(tài)數(shù)據(jù)集合，讓每個(gè)操作的時(shí)間復(fù)雜度盡可能低。答案不言而喻，作者在本節(jié)最后給出了一段分析描述。

二、堆排序：為什么說(shuō)堆排序沒(méi)有快速排序快

這一部分介紹了堆排序

• 堆排序之建堆

• 堆排序之排序

• 堆排序的性能分析

這一部分，涉及堆排序的主要內(nèi)容，各種教材都有。作者為了體現(xiàn)特色，闡述了為什么說(shuō)堆排序沒(méi)有快速排序快，給出了兩個(gè)理由。值得讀一讀。

三、堆的應(yīng)用

這一部分介紹了堆的應(yīng)用

• 優(yōu)先級(jí)隊(duì)列：合并多個(gè)有序文件；高性能定時(shí)器

• 求Top K：一個(gè)包含10億個(gè)搜索關(guān)鍵詞的日志文件，如何快速統(tǒng)計(jì)出Top 10熱門搜索關(guān)鍵詞

• 求中位數(shù)和百分位數(shù)

這一部分，體現(xiàn)了作者寫本書的風(fēng)格，從實(shí)用、面試和工業(yè)角度來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法。幾個(gè)經(jīng)典的堆應(yīng)用例子，是很多教材有利補(bǔ)充。