深入了解Java數(shù)據(jù)結(jié)構(gòu)和算法之堆

更新時間：2022年01月21日 15:19:26 作者：YSOcean

這篇文章主要為大家介紹了Java數(shù)據(jù)結(jié)構(gòu)和算法之堆，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助

1、堆的定義

①、它是完全二叉樹，除了樹的最后一層節(jié)點不需要是滿的，其它的每一層從左到右都是滿的。注意下面兩種情況，第二種最后一層從左到右中間有斷隔，那么也是不完全二叉樹。

②、它通常用數(shù)組來實現(xiàn)?！　?/p>

這種用數(shù)組實現(xiàn)的二叉樹，假設(shè)節(jié)點的索引值為index，那么：

節(jié)點的左子節(jié)點是 2*index+1，

節(jié)點的右子節(jié)點是 2*index+2，

節(jié)點的父節(jié)點是（index-1）/2。

③、堆中的每一個節(jié)點的關(guān)鍵字都大于（或等于）這個節(jié)點的子節(jié)點的關(guān)鍵字。

這里要注意堆和前面說的二叉搜索樹的區(qū)別，二叉搜索樹中所有節(jié)點的左子節(jié)點關(guān)鍵字都小于右子節(jié)點關(guān)鍵字，在二叉搜索樹中通過一個簡單的算法就可以按序遍歷節(jié)點。但是在堆中，按序遍歷節(jié)點是很困難的，如上圖所示，堆只有沿著從根節(jié)點到葉子節(jié)點的每一條路徑是降序排列的，指定節(jié)點的左邊節(jié)點或者右邊節(jié)點，以及上層節(jié)點或者下層節(jié)點由于不在同一條路徑上，他們的關(guān)鍵字可能比指定節(jié)點大或者小。所以相對于二叉搜索樹，堆是弱序的。

2、遍歷和查找

前面我們說了，堆是弱序的，所以想要遍歷堆是很困難的，基本上，堆是不支持遍歷的。

對于查找，由于堆的特性，在查找的過程中，沒有足夠的信息來決定選擇通過節(jié)點的兩個子節(jié)點中的哪一個來選擇走向下一層，所以也很難在堆中查找到某個關(guān)鍵字。

因此，堆這種組織似乎非常接近無序，不過，對于快速的移除最大（或最?。┕?jié)點，也就是根節(jié)點，以及能快速插入新的節(jié)點，這兩個操作就足夠了。

3、移除

移除是指刪除關(guān)鍵字最大的節(jié)點（或最?。簿褪歉?jié)點。

根節(jié)點在數(shù)組中的索引總是0，即maxNode = heapArray[0];

移除根節(jié)點之后，那樹就空了一個根節(jié)點，也就是數(shù)組有了一個空的數(shù)據(jù)單元，這個空單元我們必須填上。

第一種方法：將數(shù)組所有數(shù)據(jù)項都向前移動一個單元，這比較費時。

第二種方法：

①、移走根
②、把最后一個節(jié)點移動到根的位置
③、一直向下篩選這個節(jié)點，直到它在一個大于它的節(jié)點之下，小于它的節(jié)點之上為止。

具體步驟如下：

圖a表示把最后一個節(jié)點移到根節(jié)點，圖b、c、d表示將節(jié)點向下篩選到合適的位置，它的合適位置在最底層（有時候可能在中間），圖e表示節(jié)點在正確位置的情景。

注意：向下篩選的時候，將目標節(jié)點和其子節(jié)點比較，誰大就和誰交換位置。

4、插入

插入節(jié)點也很容易，插入時，選擇向上篩選，節(jié)點初始時插入到數(shù)組最后第一個空著的單元，數(shù)組容量大小增一。然后進行向上篩選的算法。

注意：向上篩選和向下不同，向上篩選只用和一個父節(jié)點進行比較，比父節(jié)點小就停止篩選了。

5、完整的Java堆代碼

首先我們要知道用數(shù)組表示堆的一些要點。若數(shù)組中節(jié)點的索引為x，則：

節(jié)點的左子節(jié)點是 2*index+1，

節(jié)點的右子節(jié)點是 2*index+2，

節(jié)點的父節(jié)點是（index-1）/2。

注意："/" 這個符號，應用于整數(shù)的算式時，它執(zhí)行整除，且得到是是向下取整的值。

package com.ys.tree.heap;
 
public class Heap {
     
    private Node[] heapArray;
    private int maxSize;
    private int currentSize;
     
    public Heap(int mx) {
        maxSize = mx;
        currentSize = 0;
        heapArray = new Node[maxSize];
    }
     
    public boolean isEmpty() {
        return (currentSize == 0)? true : false;
    }
     
    public boolean isFull() {
        return (currentSize == maxSize)? true : false;
    }
     
    public boolean insert(int key) {
        if(isFull()) {
            return false;
        }
        Node newNode = new Node(key);
        heapArray[currentSize] = newNode;
        trickleUp(currentSize++);
        return true;
    }
    //向上調(diào)整
    public void trickleUp(int index) {
        int parent = (index - 1) / 2; //父節(jié)點的索引
        Node bottom = heapArray[index]; //將新加的尾節(jié)點存在bottom中
        while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
            heapArray[index] = heapArray[parent];
            index = parent;
            parent = (parent - 1) / 2;
        }
        heapArray[index] = bottom;
    }
     
    public Node remove() {
        Node root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickleDown(0);
        return root;
    }
    //向下調(diào)整
    public void trickleDown(int index) {
        Node top = heapArray[index];
        int largeChildIndex;
        while(index < currentSize/2) { //while node has at least one child
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = leftChildIndex + 1;
            //find larger child
            if(rightChildIndex < currentSize &&  //rightChild exists?
                    heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {
                largeChildIndex = rightChildIndex;
            }
            else {
                largeChildIndex = leftChildIndex;
            }
            if(top.getKey() >= heapArray[largeChildIndex].getKey()) {
                break;
            }
            heapArray[index] = heapArray[largeChildIndex];
            index = largeChildIndex;
        }
        heapArray[index] = top;
    }
    //根據(jù)索引改變堆中某個數(shù)據(jù)
    public boolean change(int index, int newValue) {
        if(index < 0 || index >= currentSize) {
            return false;
        }
        int oldValue = heapArray[index].getKey();
        heapArray[index].setKey(newValue);
        if(oldValue < newValue) {
            trickleUp(index);
        }
        else {
            trickleDown(index);
        }
        return true;
    }
     
    public void displayHeap() {
        System.out.println("heapArray(array format): ");
        for(int i = 0; i < currentSize; i++) {
            if(heapArray[i] != null) {
                System.out.print(heapArray[i].getKey() + " ");
            }
            else {
                System.out.print("--");
            }
        }
    }
}
class Node {
    private int iData;
    public Node(int key) {
        iData = key;
    }
     
    public int getKey() {
        return iData;
    }
     
    public void setKey(int key) {
        iData = key;
    }
}