• 最大最小堆
  堆是一種經過排序的完全二叉樹，其中任一非終端節(jié)點的數(shù)據(jù)值均不大于（或不小于）其左子節(jié)點和右子節(jié)點的值。
  最大堆和最小堆是二叉堆的兩種形式。
  最大堆：根結點的鍵值是所有堆結點鍵值中最大者。
  最小堆：根結點的鍵值是所有堆結點鍵值中最小者。

• 最小堆示例

• 建立最小堆
  初始數(shù)組為：9,3,7,6,5,1,10,2
  按照完全二叉樹，將數(shù)字依次填入。
  填入后，找到最后一個結點，從它的父節(jié)點（本示例為數(shù)字6的節(jié)點）
  開始調整。根據(jù)性質，小的數(shù)字往上移動；至此，第1次調整完成。
  注意，被調整的節(jié)點，還有子節(jié)點的情況，需要遞歸進行調整。
  第二次調整，是數(shù)字6的節(jié)點數(shù)組下標小1的節(jié)點（比數(shù)字6的下標小1的節(jié)點是數(shù)字7的節(jié)點），
  用剛才的規(guī)則進行調整。以此類推，直到調整到根節(jié)點。

• 替換節(jié)點
  將堆頂刪除，把新增加的23放在堆頂。
  顯然加了數(shù)后已經不符合最小堆的特性了，我們需要將新增加的數(shù)調整到合適的位置。
  
  向下調整，將這個數(shù)與它的兩個兒子2和5比較，選擇較小的一個與它交換
  
  此時我們發(fā)現(xiàn)還是不滿足最小堆，于是繼續(xù)將23與它的兩個兒子中較小的一個交換。
  
  再交換
  

• 新增節(jié)點
  如果只是想新增一個數(shù)，而不是刪除最小值，只需要將新元素插入到末尾，再根據(jù)情況判斷新元素是否需要上移，直到滿足新的特性位置。
  加入我們現(xiàn)在要加入一個3
  
  先將3與它的父節(jié)點25比較，發(fā)現(xiàn)比父節(jié)點小，需要與父節(jié)點交換。以此類推
  

轉載于:https://www.cnblogs.com/bincoding/p/8975835.html

總結

以上是生活随笔為你收集整理的最大、最小堆的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。