Java資料結構之堆(優先佇列)的實現

2022-05-20 19:03:30

堆（優先佇列）是一種典型的資料結構，其形狀是一棵完全二元樹，一般用於求解topk問題。根據雙親節點大於等於孩子節點或雙親節點小於等於孩子節點，可分為大頂堆和小頂堆，本文實現大頂堆。

根據大頂堆的定義，大頂堆的雙親節點大於等於其孩子節點，堆頂元素最大，對於每一個子樹都是一個大頂堆，則從最後一個雙親節點進行調整為大頂堆，一直到根節點，則可構建一個大頂堆。

我們這裡採用陣列去儲存，以heap={3,2,1,5,6,4}為例，需要一個init(int[] heap)初始化方法，從最後一個雙親節點開始將heap逐漸調整為大頂堆，其中需要使用到adjust(int[] heap, int i, int end)方法。

調整過程：從最後一個雙親節點出發，如果以當前雙親節點為根的樹不符合大頂堆，則進行調整。

程式碼實現如下：

public void init(int[] heap) {
        //從最後一個雙親節點開始調整
        //逐漸往上進行調整
        for (int i = heap.length / 2 ; i > 0 ; i-- ) {
            this.adjust(heap, i, heap.length);
        }
    }

    public void adjust(int[] heap, int i, int end) {
        int j = i << 1;
        while (j <= end) {
            //找到兩個孩子節點z中較大的節點
            if (j < end && heap[j - 1] < heap[j]) {
                j = j + 1;
            }
            //如果較大節點還小於根節點，則以當前節點為根節點的
            //二元樹已經是大頂堆，不需要進行調整
            if (heap[i - 1] > heap[j - 1]) {
                break;
            }
            //進行調整，將當前節點換到較大位置，再從當前位置進行調整
            int temp = heap[i - 1];
            heap[i - 1] = heap[j - 1];
            heap[j - 1] = temp;
            i = j;
            j = i << 1;
        }
    }

構建好了大頂堆之後，我們如何求得topk呢，此時堆頂元素為top1，我們只需要將top1元素拿走，將剩下元素調整為大頂堆，k次之後即可得到topk。

具體過程：我們將堆頂元素與最後一個元素進行交換，然後將堆頂到倒數第二個元素進行調整，依次類推。

以leetcode215陣列中第k個最大元素為例：

給定整數陣列 nums 和整數 k，請返回陣列中第 k 個最大的元素。

請注意，你需要找的是陣列排序後的第 k 個最大的元素，而不是第 k 個不同的元素

public int findKthLargest(int[] nums, int k) {
        this.init(nums);
        //找到第k大的數
        int end = nums.length;
        while (k > 1) {
            //將當前堆頂元素放到末尾，進行堆調整
            int temp = nums[0];
             nums[0] = nums[end - 1];
             nums[end - 1] = temp;
             end = end - 1;
             -- k;
             this.adjust(nums, 1, end);
        }
        return nums[0];
    }

此外，Java本身提供了優先佇列集合類，但是對於這個題目效率不如自己實現的高

public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (priorityQueue.size() == k) {
                if (num > priorityQueue.peek()) {
                    priorityQueue.poll();
                    priorityQueue.add(num);
                }
                continue;
            }
            priorityQueue.add(num);
        }
        return priorityQueue.poll();
    }

到此這篇關於Java資料結構之堆(優先佇列)的實現的文章就介紹到這了,更多相關Java 堆內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java資料結構之堆(優先佇列)的實現

熱門文章