1桐罕，基礎(chǔ)知識
1）完全二叉樹脉让，雙親節(jié)點和孩子節(jié)點的關(guān)系
array[0桂敛，...，n-1]表示完全二叉樹順序存儲模式
1.節(jié)點array[i] 的父節(jié)點為 i==0 ? null : array[i-1/2]
2.節(jié)點array[i]的左孩子為溅潜，array[2*i + 1]
3.節(jié)點array[i]的右孩子為术唬，array[2*i + 2]
2）堆在數(shù)組中的表示方式
堆的邏輯結(jié)構(gòu)是一顆完全二叉樹，存儲結(jié)構(gòu)是一個數(shù)組滚澜。
數(shù)組為完全二叉樹的層次遍歷的結(jié)果粗仓。
3）大根堆和小根堆的定義
前提0 <= i < (n-1)/2
1.滿足array[i] <= array[2i + 1] && array[i] <= array[2i + 2] 為小根堆。
2.滿足array[i] >= array[2i + 1] && array[i] >= array[2i + 2] 為大根堆设捐。
2借浊，創(chuàng)建小根堆
1）調(diào)整數(shù)組為小根堆
處理非葉子節(jié)點順序從[len/2 -1 ~ 0]
調(diào)整小根堆順序，從上往下調(diào)整
image.png
2）小根堆插入
將元素放到數(shù)組末尾
和parent比較挡育，從下往上調(diào)整小根堆
image.png
3）小根堆刪除
刪除array[0] -> array[0] = array[size-1] -> array[size-1] = 0
從上往下巴碗，父節(jié)點與左右孩子的最小值比較，依次調(diào)整小根堆
image.png
image.png
3即寒，大根堆
1）調(diào)整方法橡淆。
父節(jié)點與左右子節(jié)點的最大者比較，如果小于max母赵，則交換逸爵。
image.png
2）大根堆插入
放入數(shù)組的最后一個位置
節(jié)點上浮，與父節(jié)點(i-1)/2比較
3）大根堆刪除
刪除堆頂元素 -> 將最后個元素賦值給堆頂
從上往下凹嘲，父節(jié)點與左右子孩子的最大值比較师倔，調(diào)整最大堆。
4）JDK實現(xiàn)大根堆和小跟堆
PriorityQueue：默認(rèn)為小根堆
PriorityQueue：自定義的Comparator周蹭，使用o2 - o1趋艘，實現(xiàn)大根堆
4，堆排序
1）一種選擇排序凶朗，最壞瓷胧、最好、平均負(fù)責(zé)度都為nlog(n)棚愤。
升序：借助大根堆
降序：借助小根堆
2）堆排序步驟
1.初始化數(shù)組為大根堆搓萧。
2.將array[0] 與 array[len - 1]交換
3.剩余n-1個元素重新調(diào)整為大根堆
4.重復(fù)執(zhí)行交換、調(diào)整的步驟
image.png
image.png
