個(gè)人博客:www.zhouximin.com
模型
優(yōu)先隊(duì)列 主要有 2 個(gè)方法
deleteMin（）的工作就是 找出拷邢，返回并刪除優(yōu)先隊(duì)列中最小的元素
insert（）的工作就是入隊(duì) 等價(jià)于 enqueue（）
一開始我覺得 很簡(jiǎn)單啊 用數(shù) 或者 加入的時(shí)候 先排序 后來(lái)一思考卓练。羊异。這樣 時(shí)間復(fù)雜度有點(diǎn)大了蚤假。然后繼續(xù)看了書 書上是用一種 二叉堆的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的
二叉堆
二叉堆 就是一顆被完全填滿的二叉樹
規(guī)定：一：插入的時(shí)候 必須先左 到右（先左子樹后右子樹的插入 ）
二: 父親要比孩子小弓叛；（這個(gè)規(guī)定是因?yàn)槲覀円羁斓恼业阶钚≈担?br>
一棵高為h的完全二叉樹有2的h次方 到2的h+1次方-1個(gè)節(jié)點(diǎn)
一個(gè)觀察發(fā)現(xiàn)
可以用一個(gè)數(shù)組表示 ：對(duì)于任意位置i上的元素璃弄，其左兒子在2i位置上 右兒子在2i+1的位置上 利用這一個(gè)規(guī)律可以利用數(shù)組來(lái)很好的實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 優(yōu)先隊(duì)列
insert
插入一個(gè)數(shù)據(jù)的時(shí)候 在下一個(gè)可用位置創(chuàng)建一個(gè)空穴，（這個(gè)空穴一定要有數(shù)據(jù)的不然就不是一個(gè)完全樹)牧抽。如果插入的時(shí)候沒有破壞規(guī)則 那么插入成功嘉熊；若破壞了規(guī)則 那么必定是這個(gè)數(shù)比父親節(jié)點(diǎn)的數(shù)據(jù)小，將空穴和父親換一下扬舒；當(dāng)已經(jīng)平衡了之后或者到了頂部阐肤，就將這個(gè)數(shù)據(jù)放入空穴就好了。
deleteMin
因?yàn)樽钚〉闹翟诘谝粋€(gè) 移除就好了 可是麻煩在與 第一個(gè)位置空了誰(shuí)來(lái)補(bǔ)充呢讲坎？必然是她的子節(jié)點(diǎn) 最小值在他們之間（這里不用解釋吧泽腮。。）然而她們上來(lái)后自己的位置又空缺了 那么繼續(xù)想下找直到?jīng)]有下面的數(shù)據(jù)后把最后一個(gè)數(shù)據(jù)填充上去
就好了衣赶；
