algorithm-4th 排序-優(yōu)先隊列

PriorityQueue是一種抽象數(shù)據(jù)類型芭商,它表示了一組值和對這些值的操作,支持兩種操作:刪除最大元素和插入元素。它的適用場景可能是金融事務再愈,你需要從中找出最大的那些;或是農(nóng)產(chǎn)品中的殺蟲劑含量护戳,這時你需要從
中找出最小的那些翎冲, 等等

java 版的 MaxPQ 模板

public class MaxPQ <Key extends Comparable<Key>> {
    MaxPQ(Key[] a)       用 a[] 中的元素創(chuàng)建一個優(yōu)先隊列
    void insert(Key v)   向優(yōu)先隊列中插入一個元素
    Key max()            返回最大元素
    Key delMax()         刪除并返回最大元素
    boolean isEmpty()    返回隊列是否為空
    int size()           返回優(yōu)先隊列中的元素個數(shù)
}

使用二叉堆實現(xiàn)優(yōu)先隊列

二叉堆定義

二叉堆是一組能夠用堆有序的完全二叉樹排序的元素,并在數(shù)組中按照層級儲存(不使
用數(shù)組的第一個位置)

在一個堆中媳荒,位置 k 的結點的父結點的位置為k/2抗悍,而它的兩個子結點的位置則分別為 2k 和 2k+1。在排序算法中钳枕,我們只通過私有輔助函數(shù) less() 和 exch() 來訪問元素

堆.png

用它們我們將能實現(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作缴渊。利用在數(shù)組中無需指針即可沿樹上下移動的便利和以下性質(zhì),算法保證了對數(shù)復雜度的性能鱼炒。

堆的表示.png

堆的算法

我們用長度為 N+1 的私有數(shù)組 pq[] 來表示一個大小為 N 的堆疟暖,我們不會使 用 pq[0], 堆 元 素 放 在 pq[1] 至pq[N] 中田柔。

由下至上的堆有序化(上浮 swim)

swim.png

由上至下的堆有序化(下沉 sink)

sink.png

堆的操作

插入元素: 我們將新元素加到數(shù)組末尾俐巴,增加堆的大小并讓這個新元素上浮到合適的位置

刪除最大元素: 我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端,減小堆的大小并讓這個元素下沉到合適的位置

堆的操作.png

實現(xiàn)

public class MaxPQ<Key extends Comparable<Key>> { 
     private Key[] pq; // 基于堆的完全二叉樹
     private int N = 0; // 存儲于pq[1..N]中硬爆,pq[0]沒有使用
     
     public MaxPQ(int maxN) { 
         pq = (Key[]) new Comparable[maxN+1]; 
     }
     
     public boolean isEmpty() { 
         return N == 0; 
     }
     
     public int size() { 
         return N; 
     }
     
     // 將新元素加到數(shù)組末尾欣舵,增加堆的大小并讓這個新元素上浮到合適的位置
     public void insert(Key v) { 
         pq[++N] = v; 
         swim(N); 
     }
     
     // 從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端,減小堆的大小并讓這個元素下沉到合適的位置
     public Key delMax() {
         Key max = pq[1];  // 從根結點得到最大元素
         exch(1, N--);     // 將其和最后一個結點交換
         pq[N+1] = null;   // 防止對象游離
         sink(1);          // 恢復堆的有序性
         return max; 
     }
     
     private void swim(int k) {
         while (k > 1 && less(k/2, k)) { 
             exch(k/2, k); 
             k = k/2;  // java 中向下取整
         }
     }
     
     private void sink(int k) {
         while (2*k <= N) { 
             int j = 2*k; 
             if (j < N && less(j, j+1)) j++; 
             if (!less(k, j)) break; 
             exch(k, j); 
             k = j; 
         }
     }
     
    private boolean less(int i, int j) { 
        return pq[i].compareTo(pq[j]) < 0; 
    }
     
    private void exch(int i, int j) { 
        Key t = pq[i]; 
        pq[i] = pq[j]; 
        pq[j] = t; 
    }
 
}

堆排序

public static void sort(Comparable[] a) { 
    int N = a.length; 
    
    for (int k = N/2; k >= 1; k--) { // for 循環(huán)構造了堆
        sink(a, k, N); 
    }
 
    while (N > 1) { // while 循環(huán)將最大的元素 a[1] 和 a[N] 交換并修復了堆缀磕,如此重復直到堆變空缘圈。
       exch(a, 1, N--); 
       sink(a, 1, N); 
    } 
}
堆的構造和下沉排序.png

小結

堆排序在排序復雜性的研究中有著重要的地位劣光,因為它是我們所知的唯一能夠同時最優(yōu)地利用空間和時間的方法——在最壞的情況下它也能保證使用~ 2NlgN 次比較和恒定的額外空間。

當空間十分緊張的時候(例如在嵌入式系統(tǒng)或低成本的移動設備中)它很流行糟把,因為它只用幾行就能實現(xiàn)(甚至機器碼也是)較好的性能绢涡。但現(xiàn)代系統(tǒng)的許多應用很少使用它,因為它無法利用緩存遣疯。數(shù)組元素很少和相鄰的其他元素進行比較雄可,因此緩存未命中的次數(shù)要遠遠高于大多數(shù)比較都在相鄰元素間進行的算法,如快速排序缠犀、歸并排序数苫,甚至是希爾排序。

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末辨液,一起剝皮案震驚了整個濱河市虐急,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌滔迈,老刑警劉巖止吁,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異燎悍,居然都是意外死亡赏殃,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門间涵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來仁热,“玉大人,你說我怎么就攤上這事勾哩】勾溃” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵思劳,是天一觀的道長迅矛。 經(jīng)常有香客問我,道長潜叛,這世上最難降的妖魔是什么秽褒? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮威兜,結果婚禮上销斟,老公的妹妹穿的比我還像新娘。我一直安慰自己椒舵,他們只是感情好蚂踊,可當我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著笔宿,像睡著了一般犁钟。 火紅的嫁衣襯著肌膚如雪棱诱。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天涝动,我揣著相機與錄音迈勋,去河邊找鬼。 笑死醋粟,一個胖子當著我的面吹牛靡菇,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播昔穴,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼提前!你這毒婦竟也來了吗货?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤狈网,失蹤者是張志新(化名)和其女友劉穎宙搬,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拓哺,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡勇垛,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了士鸥。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片闲孤。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖烤礁,靈堂內(nèi)的尸體忽然破棺而出讼积,到底是詐尸還是另有隱情,我是刑警寧澤脚仔,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布勤众,位于F島的核電站,受9級特大地震影響鲤脏,放射性物質(zhì)發(fā)生泄漏们颜。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一猎醇、第九天 我趴在偏房一處隱蔽的房頂上張望窥突。 院中可真熱鬧,春花似錦硫嘶、人聲如沸波岛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽则拷。三九已至贡蓖,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間煌茬,已是汗流浹背斥铺。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留坛善,地道東北人晾蜘。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像眠屎,于是被迫代替她去往敵國和親剔交。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內(nèi)容