先了解了解
什麼是二叉堆
二叉堆就是完全二叉樹,或者是靠近完全二叉樹結構的二叉樹。在二叉樹建樹時采取前序建樹就是建立的完全二叉樹。也就是二叉堆。是以二叉堆的建堆過程理論上講和前序建樹一樣。
什麼是大頂堆、小頂堆
二叉堆本質上是一棵近完全的二叉樹,那麼大頂堆和小頂堆必然也是滿足這個結構要求的。在此之上,大頂堆要求對于一個節點來說,它的左右節點都比它小;小頂堆要求對于一個節點來說,它的左右節點都比它大。
建堆
二叉堆建堆本質上和前序建堆差不多,隻不過需要考慮的一點就是大小關系,這一點和二叉搜尋樹建樹有點相似,是以可以得出結論,建樹,本質上都是遞歸建樹,隻不過因為資料結構的大小要求不一樣,需要的判斷函數不一樣,節點進入哪個位置也不一樣。
大頂堆和小頂堆也分為穩定和不穩定的堆。穩定和不穩定指如果具備相同的值,那麼他們的插入順序應該和節點順序一緻。
程式實作
首先,定義出基本的堆結構
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;
}
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
}
}