堆和堆排序在筆試題面試題中的應(yīng)用
堆和堆排序在筆試題面試題中的應(yīng)用；
使用堆解決可以解決下列幾個(gè)問(wèn)題，它們?cè)诠P試面試題中可以稱為經(jīng)典和燙手的：
1. 構(gòu)建哈夫曼代碼怎樣提升性能?
我們知道在構(gòu)建哈夫曼樹時(shí)，每次要選擇集合中兩個(gè)最小的元素，然后將元素值相加，合并為一個(gè)新節(jié)點(diǎn)，此時(shí)兩個(gè)最小的元素的取出可以用HeapExtractMin函數(shù)來(lái)實(shí)現(xiàn)，產(chǎn)出的新節(jié)點(diǎn)需要插入到堆中 我們有MinHeapInsert函數(shù)來(lái)實(shí)現(xiàn)，
堆和堆排序在筆試題面試題中的應(yīng)用
。之前我們遇到哈夫曼編碼，往往關(guān)注的是其思想，然而每次取出最小的`2個(gè)元素的過(guò)程，卻涉及到排序、求極值的問(wèn)題。這時(shí)候用堆來(lái)維護(hù)這個(gè)隊(duì)列，每次還能將取出的兩個(gè)最小值的和插到堆里，非常方便，減少了運(yùn)行時(shí)間。
2. 計(jì)算大型浮點(diǎn)數(shù)集合的和
有一個(gè)很普遍的情況，我們知道浮點(diǎn)數(shù)的存儲(chǔ)都有精度，遇到大浮點(diǎn)數(shù)和小浮點(diǎn)數(shù)相加，很可能會(huì)造成精度誤差。所以可以每次從優(yōu)先級(jí)隊(duì)列中取出最小的兩個(gè)數(shù)相加，和1的實(shí)現(xiàn)差不多，
資料共享平臺(tái)
《堆和堆排序在筆試題面試題中的應(yīng)用》(http://www.oriental01.com)。3. 在具有10億個(gè)數(shù)值的集合中找到100萬(wàn)個(gè)最大的數(shù)
這個(gè)就是TOP(K)問(wèn)題了，可以建立100萬(wàn)個(gè)元素的最小二叉堆，后面的數(shù)和根部進(jìn)行比較，如果大于根部，進(jìn)行堆調(diào)整
4. 將多個(gè)小型有序文件合并到一個(gè)大型有序文件中
該問(wèn)題我整理成了另一篇文章。里面附有源碼測(cè)試;
假設(shè)有 n個(gè) 小型有序文件，建立一個(gè)大小為n的最小堆，每個(gè)有序文件貢獻(xiàn)一個(gè)(如果有的話)，每次取出最小值插入到大型文件中，并且去掉該最小元素，并將它在文件中的后續(xù)元素插入到堆中,能夠在o(lgn)的時(shí)間內(nèi)從n個(gè)文件中選擇要插入到大型文件中的元素。
意思就是，維護(hù)一個(gè)堆，該堆存放了所有小文件的最小值。每次取出最小值min(屬于小文件A)，將小文件A的下一個(gè)最小值再插入到A。持續(xù)下去，問(wèn)題解決。
其他的相關(guān)筆試經(jīng)驗(yàn)：
農(nóng)村商業(yè)銀行筆試分享 女大學(xué)生應(yīng)聘銀行心得 經(jīng)驗(yàn)客服筆試題讓你思維靈活
【堆和堆排序在筆試題面試題中的應(yīng)用】相關(guān)文章：
1.筆試題（堆和棧）