Java實現二叉堆、大頂堆和小頂堆
什麼是二叉堆
二叉堆就是完全二叉樹,或者是靠近完全二叉樹結構的二叉樹。在二叉樹建樹時采取前序建樹就是建立的完全二叉樹。也就是二叉堆。所以二叉堆的建堆過程理論上講和前序建樹一樣。
什麼是大頂堆、小頂堆
二叉堆本質上是一棵近完全的二叉樹,那麼大頂堆和小頂堆必然也是滿足這個結構要求的。在此之上,大頂堆要求對於一個節點來說,它的左右節點都比它小;小頂堆要求對於一個節點來說,它的左右節點都比它大。
建堆
二叉堆建堆本質上和前序建堆差不多,隻不過需要考慮的一點就是大小關系,這一點和二叉搜索樹建樹有點相似,所以可以得出結論,建樹,本質上都是遞歸建樹,隻不過因為數據結構的大小要求不一樣,需要的判斷函數不一樣,節點進入哪個位置也不一樣。
大頂堆和小頂堆也分為穩定和不穩定的堆。穩定和不穩定指如果具備相同的值,那麼他們的插入順序應該和節點順序一致。
程序實現
首先,定義出基本的堆結構
public class BinaryHeap { private Integer value; private BinaryHeap leftChild; private BinaryHeap rightChild; }
建堆過程與建二叉樹過程一致
public static BinaryHeap buildHeap(BinaryHeap binaryHeap, Integer value) { if (Objects.isNull(binaryHeap)) binaryHeap = new BinaryHeap(); if (Objects.isNull(binaryHeap.getValue())) { binaryHeap.setValue(value); return binaryHeap; } if (Objects.isNull(binaryHeap.getLeftChild())) { BinaryHeap binaryHeap1 = new BinaryHeap(); binaryHeap1.setValue(value); binaryHeap.setLeftChild(binaryHeap1); } else if (Objects.nonNull(binaryHeap.getLeftChild())) { if (Objects.isNull(binaryHeap.getRightChild())) { BinaryHeap binaryHeap1 = new BinaryHeap(); binaryHeap1.setValue(value); binaryHeap.setRightChild(binaryHeap1); } else { // TODO: 2022/1/14 左右節點兩種都不為null if (checkNull(binaryHeap.getLeftChild())) buildHeap(binaryHeap.getLeftChild(), value); else if (checkNull(binaryHeap.getRightChild())) buildHeap(binaryHeap.getRightChild(), value); else buildHeap(binaryHeap.getLeftChild(), value); } } return binaryHeap; }
主要原理就是如果當前節點的左節點為空,則把當前值放到左節點,如果左節點不為空,右節點為空,則把值放到右節點。如果左右節點都不為空,就將建樹過程轉移到下一層,如果左節點有為空的子節點,就轉移給左節點,如果左節點沒有為空的子節點,且右節點有為空的子節點,那麼轉移給右節點。如果左右節點都沒有為空的子節點,那麼也轉移給左節點。
以序列2,3,4,5,9,6,8,7為例,按照該算法建立出來的二叉堆結構如下:
{ "value": 2, "left_child": { "value": 3, "left_child": { "value": 4, "left_child": { "value": 8, "left_child": null, "right_child": null }, "right_child": { "value": 7, "left_child": null, "right_child": null } }, "right_child": { "value": 5, "left_child": null, "right_child": null } }, "right_child": { "value": 1, "left_child": { "value": 9, "left_child": null, "right_child": null }, "right_child": { "value": 6, "left_child": null, "right_child": null } } }
建立大頂堆
大頂堆在建堆的基礎上,有一個要求,根節點比左右子樹的任何節點的值都大。那麼建樹的過程可以分為兩步,對於每一個值,首先按照建樹過程,會到二叉堆的最底部,然後通過不斷的讓自己與自己的根節點做比較,如果自己大於根節點,就交換自己與根節點的位置,遞歸回溯即可。
邏輯過程
假設現在紅色節點組成的已經是一個大頂堆,現在新增瞭一個節點到這個二叉堆中,而且是比任意節點都大,那麼黑色箭頭將是該節點的行動路線,它會反復與父級比較,如果大於父級,則交換和父級的關系。
程序實現
public static BinaryHeap up(BinaryHeap father) { if (Objects.nonNull(father.getLeftChild())) { if (father.getValue() < father.getLeftChild().getValue()) { int c = father.getValue(); father.setValue(father.getLeftChild().getValue()); father.getLeftChild().setValue(c); } up(father.getLeftChild()); } if (Objects.nonNull(father.getRightChild())) { if (father.getValue() < father.getRightChild().getValue()) { int c = father.getValue(); father.setValue(father.getRightChild().getValue()); father.getRightChild().setValue(c); } up(father.getRightChild()); } return father; }
該方法放在普通建樹方法之後,就是大頂堆的建樹方法瞭,總的方法如下:
public static BinaryHeap bigPush(BinaryHeap binaryHeap, Integer value) { binaryHeap = buildHeap(binaryHeap, value); up(binaryHeap); return binaryHeap; }
還是以序列2,3,4,5,9,6,8,7為例,按照該算法建立出來的大頂堆結構如下:
{ "value": 9, "left_child": { "value": 8, "left_child": { "value": 7, "left_child": { "value": 2, "left_child": null, "right_child": null }, "right_child": { "value": 4, "left_child": null, "right_child": null } }, "right_child": { "value": 3, "left_child": null, "right_child": null } }, "right_child": { "value": 6, "left_child": { "value": 1, "left_child": null, "right_child": null }, "right_child": { "value": 5, "left_child": null, "right_child": null } } }
建立小頂堆
小頂堆與大頂堆類似
邏輯過程
過程與大頂堆一致,不過此時是比父級小就和父級交換。
程序實現
public static BinaryHeap down(BinaryHeap father) { if (Objects.nonNull(father.getLeftChild())) { if (father.getValue() > father.getLeftChild().getValue()) { int c = father.getValue(); father.setValue(father.getLeftChild().getValue()); father.getLeftChild().setValue(c); } down(father.getLeftChild()); } if (Objects.nonNull(father.getRightChild())) { if (father.getValue() > father.getRightChild().getValue()) { int c = father.getValue(); father.setValue(father.getRightChild().getValue()); father.getRightChild().setValue(c); } down(father.getRightChild()); } return father; }
這個是向下走的過程,最終代碼為:
public static BinaryHeap smallPush(BinaryHeap binaryHeap, Integer value) { binaryHeap = buildHeap(binaryHeap, value); down(binaryHeap); return binaryHeap; }
以序列2,3,4,5,9,6,8,7為例,按照該算法建立出來的小頂堆結構如下:
{ "value": 1, "left_child": { "value": 3, "left_child": { "value": 4, "left_child": { "value": 8, "left_child": null, "right_child": null }, "right_child": { "value": 7, "left_child": null, "right_child": null } }, "right_child": { "value": 5, "left_child": null, "right_child": null } }, "right_child": { "value": 2, "left_child": { "value": 9, "left_child": null, "right_child": null }, "right_child": { "value": 6, "left_child": null, "right_child": null } } }
從堆頂取數據並重構大小頂堆
public static Integer bigPop(BinaryHeap binaryHeap) { Integer val = binaryHeap.getValue(); if (binaryHeap.getLeftChild().getValue() >= binaryHeap.getRightChild().getValue()) { binaryHeap.setValue(binaryHeap.getLeftChild().getValue()); BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild()); up(binaryHeap1); binaryHeap.setLeftChild(binaryHeap1); } else { binaryHeap.setValue(binaryHeap.getRightChild().getValue()); BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild()); up(binaryHeap1); binaryHeap.setRightChild(binaryHeap1); } return val; } public static Integer smallPop(BinaryHeap binaryHeap) { Integer val = binaryHeap.getValue(); if (binaryHeap.getLeftChild().getValue() <= binaryHeap.getRightChild().getValue()) { binaryHeap.setValue(binaryHeap.getLeftChild().getValue()); BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getLeftChild().getLeftChild(), binaryHeap.getLeftChild().getRightChild()); down(binaryHeap1); binaryHeap.setLeftChild(binaryHeap1); } else { binaryHeap.setValue(binaryHeap.getRightChild().getValue()); BinaryHeap binaryHeap1 = mergeTree(binaryHeap.getRightChild().getLeftChild(), binaryHeap.getRightChild().getRightChild()); down(binaryHeap1); binaryHeap.setRightChild(binaryHeap1); } return val; }
取出來之後,需要重新調用down或者up函數。以構建小頂堆,取出五次後的結果
public static void main(String[] args) { int[] a = new int[]{2, 3, 1, 4, 5, 9, 6, 8, 7}; BinaryHeap binaryHeap = new BinaryHeap(); for (int i = 0; i < a.length; i++) { binaryHeap = smallPush(binaryHeap, a[i]); } System.out.println(Json.toJson(smallPop(binaryHeap))); System.out.println(Json.toJson(smallPop(binaryHeap))); System.out.println(Json.toJson(smallPop(binaryHeap))); System.out.println(Json.toJson(smallPop(binaryHeap))); System.out.println(Json.toJson(smallPop(binaryHeap))); System.out.println(Json.toJson(binaryHeap)); }
取完後的小頂堆為:
{ "value": 6, "left_child": { "value": 7, "left_child": { "value": 8, "left_child": null, "right_child": null }, "right_child": null }, "right_child": { "value": 9, "left_child": null, "right_child": null } }
到此這篇關於Java實現二叉堆、大頂堆和小頂堆的文章就介紹到這瞭,更多相關Java內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!