快捷導(dǎo)航

Java實現(xiàn)堆算法的使用示例

更新時間：2023年12月13日 10:42:29 作者：小筱在線

本文主要介紹了Java實現(xiàn)堆算法的使用示例,Java中提供了一個Heap類,可以用來實現(xiàn)堆的操作,可以實現(xiàn)如插入、刪除、獲取最大最小值等,具有一定的參考價值,感興趣的可以了解一下

堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它是一棵完全二叉樹，且滿足堆的性質(zhì)：對于每個節(jié)點，它的值都不小于（或不大于）它的孩子節(jié)點的值。根節(jié)點的值就是堆中的最大值（或最小值）。

Java中提供了一個Heap類，可以用來實現(xiàn)堆的操作。Heap類是一個抽象類，它定義了堆的基本操作方法，如插入、刪除、獲取最大（或最?。┲档取?/p>

要使用Heap類，需要創(chuàng)建一個具體的實現(xiàn)類，例如MaxHeap和MinHeap。這些類繼承自Heap類，并實現(xiàn)了具體的插入、刪除、獲取最大（或最?。┲档确椒?。下面我們以MaxHeap為例，來詳細介紹如何實現(xiàn)堆。

MaxHeap的實現(xiàn)思路如下：

定義一個數(shù)組來保存堆的元素，數(shù)組下標(biāo)從1開始。
定義一個變量來記錄堆中元素的數(shù)量。
實現(xiàn)插入方法：新元素插入到數(shù)組最后，然后使用上濾操作將新元素沿著路徑向上移動，直到堆的性質(zhì)被滿足。
實現(xiàn)刪除方法：移除堆頂元素（數(shù)組下標(biāo)為1的元素），然后將數(shù)組最后一個元素替換到堆頂，使用下濾操作將新元素沿著路徑向下移動，直到堆的性質(zhì)被滿足。
實現(xiàn)獲取最大值方法：直接返回堆頂元素。
實現(xiàn)堆排序方法：依次取出堆頂元素，將其放到一個新的數(shù)組中，然后重新調(diào)整堆。

以下是MaxHeap的代碼實現(xiàn)：

public class MaxHeap<T extends Comparable<T>> {
    private T[] heap; // 堆元素數(shù)組
    private int size; // 堆元素數(shù)量

    @SuppressWarnings("unchecked")
    public MaxHeap(int capacity) {
        heap = (T[]) new Comparable[capacity + 1]; // 數(shù)組下標(biāo)從1開始
        size = 0;
    }

    public void insert(T value) {
        if (size == heap.length - 1) {
            resize();
        }

        heap[++size] = value; // 新元素插入到數(shù)組最后
        swim(size); // 上濾操作
    }

    public T deleteMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }

        T max = heap[1]; // 堆頂元素
        heap[1] = heap[size--]; // 將數(shù)組最后一個元素替換到堆頂
        sink(1); // 下濾操作
        heap[size + 1] = null; // 釋放舊的堆頂元素

        return max;
    }

    public T getMax() {
        if (size == 0) {
            throw new NoSuchElementException();
        }

        return heap[1];
    }

    public void heapSort(T[] arr) {
        heapify(arr); // 初始化堆
        for (int i = size; i > 0; i--) {
            arr[i - 1] = deleteMax(); // 依次取出堆頂元素
        }
    }

    private void swim(int k) {
        while (k > 1 && heap[k].compareTo(heap[k / 2]) > 0) { // 父節(jié)點小于當(dāng)前節(jié)點，上濾
            swap(k, k / 2);
            k /= 2; // 移動到父節(jié)點
        }
    }

    private void sink(int k) {
        while (2 * k <= size) { // 如果有左孩子
            int j = 2 * k;
            if (j < size && heap[j].compareTo(heap[j + 1]) < 0) { // 選擇左右孩子中較大的那個
                j++;
            }

            if (heap[k].compareTo(heap[j]) >= 0) { // 如果父節(jié)點不小于孩子節(jié)點，下濾結(jié)束
                break;
            }

            swap(k, j); // 父節(jié)點和子節(jié)點交換
            k = j; // 移動到子節(jié)點
        }
    }

    private void heapify(T[] arr) {
        heap = (T[]) new Comparable[arr.length + 1];
        size = arr.length;

        System.arraycopy(arr, 0, heap, 1, arr.length); // 復(fù)制數(shù)組元素到堆中

        for (int i = size / 2; i >= 1; i--) { // 倒序下濾，從最后一個非葉子節(jié)點開始
            sink(i); // 下濾操作
        }
    }

    private void resize() {
        int newSize = heap.length * 2;
        heap = Arrays.copyOf(heap, newSize);
    }

    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

上面的代碼實現(xiàn)了MaxHeap類，它支持插入、刪除、獲取最大值和堆排序等操作。堆排序的實現(xiàn)就是先將數(shù)組元素初始化成一個堆，然后依次取出堆頂元素，進行排序。

MaxHeap類中使用了泛型，可以存儲任意類型的元素，只要實現(xiàn)了Comparable接口。使用時，可以像下面這樣創(chuàng)建一個MaxHeap對象，然后調(diào)用其方法進行操作：

MaxHeap<Integer> maxHeap = new MaxHeap<>(10);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(1);
maxHeap.insert(5);
System.out.println(maxHeap.deleteMax()); // 輸出：5
System.out.println(maxHeap.getMax()); // 輸出：4

Integer[] arr = {3, 1, 4, 1, 5};
maxHeap.heapSort(arr);
System.out.println(Arrays.toString(arr)); // 輸出：[1, 1, 3, 4, 5]

總的來說，實現(xiàn)堆的關(guān)鍵在于實現(xiàn)上濾和下濾操作。上濾操作用于插入新元素時，將其從葉子節(jié)點沿著路徑向上移動，下濾操作用于刪除堆頂元素時，將最后一個元素從根節(jié)點沿著路徑向下移動，維護堆的性質(zhì)。堆排序的實現(xiàn)就是先將數(shù)組初始化成一個堆，然后依次取出堆頂元素，進行排序。最后，需要注意的是，在Java中實現(xiàn)堆可以使用Heap類，但也可以自己實現(xiàn)一個堆類，可以根據(jù)具體需求進行設(shè)計和優(yōu)化。

到此這篇關(guān)于Java實現(xiàn)堆算法的使用示例的文章就介紹到這了,更多相關(guān)Java 堆算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: