堆和堆排序在筆試題面試題中的應用

才智咖 人氣:2.3W

   堆和堆排序在筆試題面試題中的應用;

堆和堆排序在筆試題面試題中的應用

      使用堆解決可以解決下列幾個問題,它們在筆試面試題中可以稱為經典和燙手的:

1. 構建哈夫曼程式碼怎樣提升效能?

我們知道在構建哈夫曼樹時,每次要選擇集合中兩個最小的元素,然後將元素值相加,合併為一個新節點,此時兩個最小的元素的.取出可以用HeapExtractMin函式來實現,產出的新節點需要插入到堆中 我們有MinHeapInsert函式來實現。

之前我們遇到哈夫曼編碼,往往關注的是其思想,然而每次取出最小的2個元素的過程,卻涉及到排序、求極值的問題。這時候用堆來維護這個佇列,每次還能將取出的兩個最小值的和插到堆裡,非常方便,減少了執行時間。

2. 計算大型浮點數集合的和

有一個很普遍的情況,我們知道浮點數的儲存都有精度,遇到大浮點數和小浮點數相加,很可能會造成精度誤差。所以可以每次從優先順序佇列中取出最小的兩個數相加,和1的實現差不多。

3. 在具有10億個數值的集合中找到100萬個最大的數

這個就是TOP(K)問題了,可以建立100萬個元素的最小二叉堆,後面的數和根部進行比較,如果大於根部,進行堆調整

4. 將多個小型有序檔案合併到一個大型有序檔案中

該問題我整理成了另一篇文章。裡面附有原始碼測試;

假設有 n個 小型有序檔案,建立一個大小為n的最小堆,每個有序檔案貢獻一個(如果有的話),每次取出最小值插入到大型檔案中,並且去掉該最小元素,並將它在檔案中的後續元素插入到堆中,能夠在o(lgn)的時間內從n個檔案中選擇要插入到大型檔案中的元素。

意思就是,維護一個堆,該堆存放了所有小檔案的最小值。每次取出最小值min(屬於小檔案A),將小檔案A的下一個最小值再插入到A。持續下去,問題解決。

其他的相關筆試經驗:

農村商業銀行筆試分享    女大學生應聘銀行心得    經驗客服筆試題讓你思維靈活