目錄

9.1.概述

?9.2.操作

9.2.1.插入

9.2.2.刪除

9.2.3.代碼實現(xiàn)

9.1.概述

概念：

根節(jié)點是自己所在子樹中的最值的完全二叉樹。

根節(jié)點是所在子樹的最大值，稱為大頂堆。

根節(jié)點是所在子樹的最小值，稱為小頂堆。

堆的任何子樹的根節(jié)點到子樹上的任意節(jié)點，路徑上的節(jié)點都是有序的，大頂堆為降序，小頂堆為升序。

此處展示一個大頂堆：

作用：

堆一般用來在大量數(shù)據(jù)中找到前N大或者前N小的數(shù)據(jù)。

存儲：

一般用數(shù)組來存儲堆，首先因為堆一般是從空樹開始建立的，不論如何操作其一定會是一顆完全二叉樹，不存在大量非葉子結點沒有左右孩子的情況，所以用數(shù)組來表示不會造成內(nèi)存浪費。其次堆的刪除操作需要從葉節(jié)點反向向根結點方向遍歷，鏈表結構不太好支持這種反向遍歷。

?9.2.操作

9.2.1.插入

堆的插入采用尾插法，新入堆的節(jié)點掛在最后一個葉節(jié)點上，然后往上?。ń粨Q位置）。

假設已有一顆樹，是按照44、25、31、18、10的插入順序建樹的。

假設插入的是20：

?假設插入的是35：

9.2.2.刪除

堆的刪除操作，從葉子結點開始刪除的話，直接刪除即可，不會有任何影響，只有在刪除非葉子結點時才要考慮進行結點間的調(diào)整，保持堆是大頂堆或者小頂堆。

堆在使用時每次彈出的都是堆頂?shù)臄?shù)據(jù)，因此刪除操作都是針對堆頂元素的，此處以大頂堆的刪除操作為例：

用最末尾的葉節(jié)點替換根節(jié)點，然后新的根節(jié)點與左右孩子比較是否為最大值，若不為最大值，則與參與比較的三個節(jié)點中的最大值互換位置，然后遞歸以上過程，出口為到達葉節(jié)點或者到達合適位置。文章來源地址http://www.zghlxwxcb.cn/news/detail-462483.html

9.2.3.代碼實現(xiàn)

package linearStructure.tree.heap;

import java.util.ArrayList;
import java.util.List;

public class MaxTopHeap {
    //存儲堆的數(shù)組
    private int[] heap;
    //堆的最大存儲容量
    private int maxSize;
    //當前堆的存儲數(shù)量
    private int heapSize;
    public MaxTopHeap(int maxSize) {
        this.heap = new int[maxSize];
        this.maxSize = maxSize;
        this.heapSize = 0;
    }
    // 判斷是否為空的方法
    public boolean isEmpty() {
        return heapSize == 0;
    }

    // 判斷是否填滿
    public boolean isFull() {
        return heapSize == maxSize;
    }

    // 獲取堆頂?shù)闹?    public int peek() throws Exception {
        if (heapSize == 0) {
            throw new Exception("heap is empty");
        }
        return heap[0];
    }

    // 往堆中添加值
    public void insert (int value) throws Exception {
        if (heapSize == maxSize) {
            throw new Exception("head is full");
        }
        heap[heapSize] = value;
        heapSize++;
        buildMaxHeap(heap);
    }

    // 刪除堆頂值
    public int poll() throws Exception {
        if (heapSize == 0) {
            throw new Exception("heap is empty");
        }
        int ans = heap[0];
        swap(heap,0,--heapSize);
        buildMaxHeap(heap);
        return ans;
    }

    // 建大頂堆
    private int[] buildMaxHeap(int[] array) {
        for (int i = (heapSize-2)/2; i >= 0; i--) {
            adjustDownToUp(array,i,heapSize);
        }
        return array;
    }

    private void adjustDownToUp(int[] array, int index, int length) {
        int temp = array[index];
        for (int i = 2*index+1; i < length; i = 2*i+1) {
            if (i < length-1 && array[i] < array[i+1]) {
                i++;
            }
            if (temp >= array[i]) {
                break;
            } else {
                array[index] = array[i];
                index = i;
            }
        }
        array[index] = temp;
    }
    // 交換元素值
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 獲取所有元素
    public List<Integer> getAllElements() {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < heapSize; i++) {
            ans.add(heap[i]);
        }
        return ans;
    }
}

到了這里，關于數(shù)據(jù)結構（9）樹形結構——大頂堆、小頂堆的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！