在 Java 中实现最小堆

Rupam Yadav 2023年1月30日 2021年10月2日
  1. Java 中不使用库的最小堆实现
  2. Java 中使用 PriorityQueue 实现最小堆
在 Java 中实现最小堆

最小堆是其中每个内部节点都小于或等于其子节点值的堆。我们将在以下几点中看到如何使用和不使用库来实现最小堆。

Java 中不使用库的最小堆实现

在这个例子中,我们看到了不使用任何库的实现。在这里,我们创建了一个类 JavaMinHeap,我们在其中创建了三个实例变量 HeapArray 是一个 int 类型的数组,它将保留堆的所有值,size 是堆的大小,maxSize 存储 HeapArray 的最大大小。我们还创建了一个类型为 intstatic 变量 FRONT 并将其初始化为 1。

我们在构造函数中获取 maxSize 作为参数并将其存储在实例变量 maxSize 中。我们用 0 初始化 size,用 maxSize + 1 大小的 int 数组初始化 HeapArray。我们将 Integer 的最小值存储在 HeapArray 的第一个索引处。

现在我们创建方法来在堆上执行操作。parent() 函数将 position 作为参数,并返回节点所传递位置的父节点。然后我们创建 leftChild(),它返回作为参数接收到的位置的左孩子。使用 rightChild() 返回 (2 * position) + 1 节点值的右子节点也是如此。

isLeaf() 检查一个节点是否是叶子节点,这意味着它有任何子节点。swapNodes() 是一种将位置 fpos 的节点值与位置 spos 交换的方法。在方法中,我们创建了一个 temp 变量并初始化它,HeapArrayfpos 位置,并将 HeapArrayspos 值存储到 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 实现最小堆

在这个程序中,我们使用用于创建最大和最小堆的 PriorityQueuePriorityQueue 提供了多个类似 add() 将元素插入队列的方法,peek() 获取队列的头部并将其删除,poll() 也检索队列的头部但不删除它. contains() 检查它指定的元素是队列。remove() 删除指定的元素。

我们结合 PriorityQueue 的所有功能来创建和执行最小堆操作。首先,我们使用 new PriorityQueue() 创建一个 Integer 类型的空 priorityQueue 对象。然后我们使用 add() 方法添加我们的元素。为了打印和移除队列头,我们调用打印 10 的 priorityQueue.peek()。然后我们使用增强的 for 打印队列的所有元素。现在我们调用 poll() 打印并删除 10。然后我们从队列中删除一个元素。我们使用返回 booleancontains() 来检查元素是否在队列中。最后,为了打印剩余的值,我们使用 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
Author: Rupam Yadav
Rupam Yadav avatar Rupam Yadav avatar

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

相关文章 - Java Heap