普林斯頓算法中級(jí)筆記7(優(yōu)先隊(duì)列)


什么是優(yōu)先隊(duì)列

一個(gè)普通隊(duì)列在刪除時(shí)郁稍,刪除最大或者最小的元素

方法定義
方法
MaxPQ() 創(chuàng)建一個(gè)空隊(duì)列
MaxPQ(Key[] a) 創(chuàng)建一個(gè)具有初始化數(shù)據(jù)的隊(duì)列
void insert(Key v) 插入
Key delMax() 刪除最大元素磅废,并返回該元素
boolean isEmpty() 是否為空
Key max() 返回最大元素
int size() 返回隊(duì)列大小

二叉樹(后面將之成為堆)

節(jié)點(diǎn)為N的二叉樹纳像,高度為lgN

大(小)頂堆

每一個(gè)父節(jié)點(diǎn)都不小于它的子節(jié)點(diǎn)

數(shù)組實(shí)現(xiàn)二叉樹結(jié)構(gòu)

以索引1作為起始,1的位置存儲(chǔ)根結(jié)點(diǎn)拯勉,節(jié)點(diǎn)n的子節(jié)點(diǎn)為2n,2n+1竟趾,節(jié)點(diǎn)k的子節(jié)點(diǎn)為k/2


屏幕快照 2018-08-14 下午4.55.41.png
節(jié)點(diǎn)的提升

首先針對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行處理
循環(huán)比較,它與它的父節(jié)點(diǎn)宫峦,若大于父節(jié)點(diǎn)則進(jìn)行交換岔帽。

private void swim(int k)
{
 while (k > 1 && less(k/2, k))
 {
 exch(k, k/2);
 k = k/2;
 }
}
節(jié)點(diǎn)的插入
public void insert(Key x)
{
 pq[++N] = x;
 swim(N);
}
節(jié)點(diǎn)的下降

若節(jié)點(diǎn)小于子節(jié)點(diǎn),則將次節(jié)點(diǎn)循環(huán)下降

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;
 }
}
刪除最大元素

將最頂部元素與末尾元素交換导绷,而后輸出末尾元素犀勒,并且將交換后的頂部元素再進(jìn)行sink

public Key delMax()
{
 Key max = pq[1];
 exch(1, N--);
 sink(1);
 pq[N+1] = null;
 return max;
} 
算法復(fù)雜度分析
方法 復(fù)雜度
insert logN
delMax logN

堆排序

思路
  • 構(gòu)造一個(gè)大頂堆,取堆頂元素妥曲,將堆頂元素與最后一個(gè)元素交換贾费。
  • 將剩余元素重新構(gòu)成一個(gè)大頂堆
代碼實(shí)現(xiàn)
public class Heap
{
 public static void sort(Comparable[] a)
 {
 int N = a.length;
 for (int k = N/2; k >= 1; k--)
 sink(a, k, N);
 while (N > 1)
 {
 exch(a, 1, N);
 sink(a, 1, --N);
 }
 }
}
算法復(fù)雜度與特點(diǎn)分析
  • 堆排序的算法復(fù)雜度為2NlogN,最壞為2NlogN,最好為NlogN
  • 它是一個(gè)占用額外空間很小的算法
  • 它是一個(gè)不穩(wěn)定算法
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末檐盟,一起剝皮案震驚了整個(gè)濱河市褂萧,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌遵堵,老刑警劉巖箱玷,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異陌宿,居然都是意外死亡锡足,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門壳坪,熙熙樓的掌柜王于貴愁眉苦臉地迎上來舶得,“玉大人,你說我怎么就攤上這事爽蝴°迮” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵蝎亚,是天一觀的道長(zhǎng)九孩。 經(jīng)常有香客問我,道長(zhǎng)发框,這世上最難降的妖魔是什么躺彬? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮梅惯,結(jié)果婚禮上宪拥,老公的妹妹穿的比我還像新娘。我一直安慰自己铣减,他們只是感情好她君,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著葫哗,像睡著了一般缔刹。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上劣针,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天桨螺,我揣著相機(jī)與錄音,去河邊找鬼酿秸。 笑死灭翔,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的辣苏。 我是一名探鬼主播肝箱,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼稀蟋!你這毒婦竟也來了煌张?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤退客,失蹤者是張志新(化名)和其女友劉穎骏融,沒想到半個(gè)月后链嘀,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡档玻,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年怀泊,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片误趴。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡霹琼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出凉当,到底是詐尸還是另有隱情枣申,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布看杭,位于F島的核電站忠藤,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏楼雹。R本人自食惡果不足惜熄驼,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望烘豹。 院中可真熱鬧瓜贾,春花似錦、人聲如沸携悯。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至,卻和暖如春斑唬,著一層夾襖步出監(jiān)牢的瞬間粪般,已是汗流浹背尝哆。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工频蛔, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人照雁。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓蚕愤,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親饺蚊。 傳聞我的和親對(duì)象是個(gè)殘疾皇子萍诱,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

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

  • 1 序 2016年6月25日夜,帝都污呼,天下著大雨裕坊,拖著行李箱和同學(xué)在校門口照了最后一張合照,搬離寢室打車去了提前租...
    RichardJieChen閱讀 5,109評(píng)論 0 12
  • 課程介紹 先修課:概率統(tǒng)計(jì)燕酷,程序設(shè)計(jì)實(shí)習(xí)籍凝,集合論與圖論 后續(xù)課:算法分析與設(shè)計(jì)周瞎,編譯原理,操作系統(tǒng)饵蒂,數(shù)據(jù)庫(kù)概論声诸,人...
    ShellyWhen閱讀 2,300評(píng)論 0 3
  • 1 初級(jí)排序算法 排序算法關(guān)注的主要是重新排列數(shù)組元素,其中每個(gè)元素都有一個(gè)主鍵苹享。排序算法是將所有元素主鍵按某種方...
    深度沉迷學(xué)習(xí)閱讀 1,416評(píng)論 0 1
  • 從康定情歌往雅安方向走,途徑瀘定浴麻!停留了一個(gè)晚上得问,目睹和體驗(yàn)了飛奪瀘定橋的驚悚!走在橋上一抖一抖的软免,深怕一個(gè)踩空掉...
    CindyZhong閱讀 347評(píng)論 0 0
  • “本文參加#未完待續(xù)膏萧,就要表白#活動(dòng)漓骚,本人承諾,文章內(nèi)容為原創(chuàng)榛泛,且未在其他平臺(tái)發(fā)表過蝌蹂。” 張愛玲說:“短的是生命曹锨,...
    fantasy2me閱讀 870評(píng)論 3 3