在 Java 中實現最小堆
最小堆是其中每個內部節點都小於或等於其子節點值的堆。我們將在以下幾點中看到如何使用和不使用庫來實現最小堆。
Java 中不使用庫的最小堆實現
在這個例子中,我們看到了不使用任何庫的實現。在這裡,我們建立了一個類 JavaMinHeap
,我們在其中建立了三個例項變數 HeapArray
是一個 int
型別的陣列,它將保留堆的所有值,size
是堆的大小,maxSize
儲存 HeapArray
的最大大小。我們還建立了一個型別為 int
的 static
變數 FRONT
並將其初始化為 1。
我們在建構函式中獲取 maxSize
作為引數並將其儲存在例項變數 maxSize
中。我們用 0 初始化 size
,用 maxSize + 1
大小的 int
陣列初始化 HeapArray
。我們將 Integer
的最小值儲存在 HeapArray
的第一個索引處。
現在我們建立方法來在堆上執行操作。parent()
函式將 position
作為引數,並返回節點所傳遞位置的父節點。然後我們建立 leftChild()
,它返回作為引數接收到的位置的左孩子。使用 rightChild()
返回 (2 * position) + 1
節點值的右子節點也是如此。
isLeaf()
檢查一個節點是否是葉子節點,這意味著它有任何子節點。swapNodes()
是一種將位置 fpos
的節點值與位置 spos
交換的方法。在方法中,我們建立了一個 temp
變數並初始化它,HeapArray
的 fpos
位置,並將 HeapArray
的 spos
值儲存到 HeapArray[fpos]
。現在我們將 temp
值儲存在 HeapArray[spos]
中。
convertToMinHeap()
使用 isLeaf
檢查作為引數接收的位置是否是葉子,如果不是,則檢查 HeapArray
位置的當前值是否大於左孩子或右孩子。然後我們檢查左孩子是否小於右孩子,如果是,我們使用 swapNodes()
來交換節點並在 position
處傳遞 position
和左孩子。我們再次使用 convertToMinHeap()
將接收到的左子節點轉換為最小堆。
我們使用 insert()
將值插入到最小堆中。在 insert()
中,如果陣列達到 maxSize
,我們不插入就返回;如果沒有,我們在 ++size
處獲取位置並將接收到的元素插入 HeapArray[++size]
。我們把尺寸
放到當前
。如果當前
位置的元素小於其父元素,我們將建立一個迴圈並交換節點。
為了列印最小堆,我們建立 printheap()
並迴圈遍歷 HeapArray
,其中父項位於 ith
位置,左子項位於 2 * i
位置,右子項是在 2 * i + 1
位置。在 main()
函式中,我們使用 insert()
在堆中插入元素。
public class JavaMinHeap {
private final int[] HeapArray;
private int size;
private final int maxsize;
private static final int FRONT = 1;
public JavaMinHeap(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
HeapArray = new int[this.maxsize + 1];
HeapArray[0] = Integer.MIN_VALUE;
}
private int parent(int position) {
return position / 2;
}
private int leftChild(int position) {
return (2 * position);
}
private int rightChild(int position) {
return (2 * position) + 1;
}
private boolean isLeaf(int position) {
if (position >= (size / 2) && position <= size) {
return true;
}
return false;
}
private void swapNodes(int fpos, int spos) {
int temp;
temp = HeapArray[fpos];
HeapArray[fpos] = HeapArray[spos];
HeapArray[spos] = temp;
}
private void convertToMinHeap(int position) {
if (!isLeaf(position)) {
if (HeapArray[position] > HeapArray[leftChild(position)]
|| HeapArray[position] > HeapArray[rightChild(position)]) {
if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
swapNodes(position, leftChild(position));
convertToMinHeap(leftChild(position));
} else {
swapNodes(position, rightChild(position));
convertToMinHeap(rightChild(position));
}
}
}
}
public void insert(int element) {
if (size >= maxsize) {
return;
}
HeapArray[++size] = element;
int current = size;
while (HeapArray[current] < HeapArray[parent(current)]) {
swapNodes(current, parent(current));
current = parent(current);
}
}
public void printHeap() {
for (int i = 1; i <= size / 2; i++) {
System.out.println("PARENT : " + HeapArray[i]);
System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);
System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
System.out.println();
}
}
public static void main(String[] arg) {
System.out.println("The Min Heap is ");
JavaMinHeap minHeap = new JavaMinHeap(10);
minHeap.insert(10);
minHeap.insert(2);
minHeap.insert(7);
minHeap.insert(15);
minHeap.insert(90);
minHeap.insert(19);
minHeap.insert(8);
minHeap.insert(22);
minHeap.insert(9);
minHeap.printHeap();
}
}
輸出:
The Min Heap is
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7
PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90
PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8
PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15
Java 中使用 PriorityQueue
實現最小堆
在這個程式中,我們使用用於建立最大和最小堆的 PriorityQueue
。PriorityQueue
提供了多個類似 add()
將元素插入佇列的方法,peek()
獲取佇列的頭部並將其刪除,poll()
也檢索佇列的頭部但不刪除它. contains()
檢查它指定的元素是佇列。remove()
刪除指定的元素。
我們結合 PriorityQueue
的所有功能來建立和執行最小堆操作。首先,我們使用 new PriorityQueue()
建立一個 Integer
型別的空 priorityQueue
物件。然後我們使用 add()
方法新增我們的元素。為了列印和移除佇列頭,我們呼叫列印 10 的 priorityQueue.peek()
。然後我們使用增強的 for
列印佇列的所有元素。現在我們呼叫 poll()
列印並刪除 10。然後我們從佇列中刪除一個元素。我們使用返回 boolean
的 contains()
來檢查元素是否在佇列中。最後,為了列印剩餘的值,我們使用 toArray()
將佇列轉換為陣列。
import java.util.*;
public class JavaMinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(15);
priorityQueue.add(25);
priorityQueue.add(200);
System.out.println("The head value using peek(): " + priorityQueue.peek());
System.out.println("The queue elements: ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.poll();
System.out.println("After removing the head element using poll(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.remove(25);
System.out.println("After removing 25 with remove(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
boolean b = priorityQueue.contains(15);
System.out.println("Check if priorityQueue contains 15 using contains(): " + b);
Object[] arr = priorityQueue.toArray();
System.out.println("Values in array: ");
for (Object o : arr) System.out.println("Value: " + o.toString());
}
}
輸出:
The head value using peek(): 10
The queue elements:
10
15
25
200
After removing the head element using poll():
15
200
25
After removing 25 with remove():
15
200
Check if priorityQueue contains 15 using contains(): true
Values in array:
Value: 15
Value: 200
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn