數(shù)據(jù)結(jié)構(gòu)與算法——堆

hankkin 發(fā)布于2019-08-16 16:18 / 3192人閱讀

摘要：堆排序的時(shí)間復(fù)雜度非常的穩(wěn)定，是，并且是原地排序算法，具體是怎么實(shí)現(xiàn)的呢我們一般把堆排序分為兩個(gè)步驟建堆和排序。

1. 什么是堆

堆（Heap），其實(shí)是一種特殊的二叉樹，主要滿足了二叉樹的兩個(gè)條件：

堆是一種完全二叉樹，還記得完全二叉樹的定義嗎？葉節(jié)點(diǎn)都在最底下兩層，最后一層的節(jié)點(diǎn)都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大，這種樹叫做完全二叉樹。

堆中的每個(gè)節(jié)點(diǎn)的值都必須大于等于（或者小于等于）其左右子節(jié)點(diǎn)的值。

對(duì)于堆中的每個(gè)節(jié)點(diǎn)都大于等于其左右子節(jié)點(diǎn)的值，叫做大頂堆，反之，則叫做小頂堆。看看下面的圖就能懂了。

其中，1 是大頂堆，2 是小頂堆，3 不是堆。

2. 堆是如何存儲(chǔ)的？

其實(shí)，堆可以按照完全二叉樹的存儲(chǔ)方式來儲(chǔ)存，因?yàn)橥耆鏄涫潜容^省空間的，所以我們可以直接用數(shù)組來存儲(chǔ)，然后按照數(shù)組下標(biāo)來取出堆中數(shù)據(jù)。參照下圖，來看看堆的存儲(chǔ)：

其中，對(duì)于任意位置上的節(jié)點(diǎn) i ，其左子節(jié)點(diǎn)是 2 * i + 1，右子節(jié)點(diǎn)是 2 * i + 2，父節(jié)點(diǎn)是 (i - 1) / 2。

3. 堆的幾種操作

明白了堆是怎樣儲(chǔ)存的，我們?cè)趤砜纯炊炎畛Ｒ姷膬蓚€(gè)操作：往堆中插入元素和刪除堆頂元素。

首先，如果要往堆中插入一個(gè)元素，我們先將其插入到數(shù)組中最后一個(gè)位置，然后與其父節(jié)點(diǎn)的值進(jìn)行比較，如果大于父節(jié)點(diǎn)，則交換位置，繼續(xù)比較?？纯聪旅娴膱D你就明白了：

交換操作的代碼，我也放到這里：

public class Heap {
    private int[] data;//存儲(chǔ)堆數(shù)據(jù)的數(shù)組
    private int n;//堆中可存儲(chǔ)的元素容量
    private int size;//堆中存儲(chǔ)的元素個(gè)數(shù)

    public Heap(int capacity) {
        this.data = new int[capacity];
        this.n = capacity;
        this.size = 0;
    }

    //往堆中插入數(shù)據(jù)
    public void insert(int value){
        if (size >= n) return;//堆滿了
        data[size] = value;
        int i = size;

        while ((i - 1) / 2 >= 0 && data[i] > data[(i - 1) / 2]){
            //交換data[i] 極其父節(jié)點(diǎn) data[(i - 1) / 2] 的值
            swap(data, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
        size ++;
    }
    
    //交換數(shù)組兩個(gè)位置的元素
    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

接下來看看第二種操作：刪除堆頂元素。

根據(jù)堆的定義，堆頂元素其實(shí)就是堆的最大或最小元素。所以刪除堆頂元素，我們只需要移除數(shù)組中的第 0 個(gè)元素，然后再進(jìn)行堆化，讓堆繼續(xù)保持順序。那該怎么進(jìn)行堆化呢？

首先我們直接將堆中的最后一個(gè)元素移到堆頂，然后與其左右子節(jié)點(diǎn)的值進(jìn)行比較，找到較大的那么子節(jié)點(diǎn)，交換位置，然后繼續(xù)比較，你可以結(jié)合代碼來理解一下：

    //刪除數(shù)據(jù)，如果是大頂堆，則刪除的是堆中的最大元素
    //如果是小頂堆，則刪除的堆中的最小元素
    public int removeMax(){
        if (size == 0) return -1;//堆為空
        //將數(shù)組中的最后一個(gè)元素，放到第一個(gè)位置
        int result = data[0];
        data[0] = data[size - 1];
        data[-- this.size] = 0;
        //進(jìn)行堆化
        heapify(data, size, 0);
        return result;
    }
    
    //堆化函數(shù)
    private void heapify(int[] data, int size, int i){
        while (true){
            int max = i;
            if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) max = 2 * i + 1;
            if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) max = 2 * i + 2;
            if (max == i) break;
            swap(data, i, max);
            i = max;
        }
    }

4. 堆排序

現(xiàn)在來看看里用堆這種數(shù)據(jù)結(jié)構(gòu)是怎么實(shí)現(xiàn)排序功能的。堆排序的時(shí)間復(fù)雜度非常的穩(wěn)定，是O(nlogn)，并且是原地排序算法，具體是怎么實(shí)現(xiàn)的呢？我們一般把堆排序分為兩個(gè)步驟：建堆和排序。

建堆
對(duì)于一個(gè)未排序的數(shù)組，例如 data[3,5,8,2,1,4,6]，其原始的結(jié)構(gòu)是這樣的：

可以看到第一個(gè)非葉子節(jié)點(diǎn)是 8，所以我們從 8 開始從上往下堆化，然后依次是 5 - 3，堆化后的效果就是這樣的：

這樣，我們就將一個(gè)無序的數(shù)組堆化成了具有堆的性質(zhì)的數(shù)據(jù)，還需要說明以下，如果確定一個(gè)堆的第一個(gè)非葉子節(jié)點(diǎn)是多少呢？實(shí)際上，對(duì)于長(zhǎng)度為 length 的數(shù)組，(length - 2) / 2下標(biāo)對(duì)應(yīng)的數(shù)據(jù)，就是堆中的第一個(gè)非葉子節(jié)點(diǎn)。接下來的操作就是排序了。

排序
排序的過程類似于上面說到的刪除堆頂元素，因?yàn)槎秧斣厥嵌训淖畲蠡蜃钚≡?，以大頂堆為例，我們只需要將堆頂元素和?shù)組中最后一個(gè)元素交換位置，然后重新構(gòu)造堆，繼續(xù)交換堆頂元素和數(shù)組中最后一個(gè)未排序數(shù)據(jù)，知道堆中元素剩下最后一個(gè)。

示意圖如下：

整個(gè)建堆和排序的實(shí)現(xiàn)的代碼也貼在這里：

    //堆排序
    public void heapSort(int[] data){
        int length = data.length;
        if (length <= 1) return;
        //建堆
        buildHeap(data);

        while (length > 0){
            swap(data, 0, --length);
            heapify(data, length, 0);
        }
    }
    //建堆
    //從非葉子節(jié)點(diǎn)依次堆化
    private void buildHeap(int[] data){
        int length = data.length;
        for (int i = (length - 2) / 2; i >= 0; -- i) {
            heapify(data, length, i);
        }
    }

GPU云服務(wù)器云服務(wù)器堆排序算法算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法教程

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/74035.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

hankkin

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

Python使用Numpy實(shí)現(xiàn)Kmeans算法

閱讀 3298·2021-11-12 10:36
viewport&像素

閱讀 1450·2019-08-30 15:56
什么是 CSS？

閱讀 2552·2019-08-30 11:26
CSS Modules實(shí)踐

閱讀 643·2019-08-29 13:00
CSS

閱讀 3661·2019-08-28 18:08
微信小程序?qū)嵺`_4顯示新聞（1）

閱讀 2821·2019-08-26 17:18
復(fù)習(xí)Javascript專題（二）：閉包，內(nèi)存，以及垃圾回收機(jī)制

閱讀 1961·2019-08-26 13:26
css3動(dòng)畫整理

閱讀 2487·2019-08-26 11:39

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

數(shù)據(jù)結(jié)構(gòu)與算法——堆

相關(guān)文章

**JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序**

**JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十一）二叉堆**

七大排序算法總結(jié)(java)

JVM 一套卷，助你快速掌握優(yōu)化法則

**JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總**

發(fā)表評(píng)論

0條評(píng)論

hankkin

男|高級(jí)講師

TA的文章

Python使用Numpy實(shí)現(xiàn)Kmeans算法

viewport&像素

什么是 CSS？

CSS Modules實(shí)踐

CSS

微信小程序?qū)嵺`_4顯示新聞（1）

復(fù)習(xí)Javascript專題（二）：閉包，內(nèi)存，以及垃圾回收機(jī)制

css3動(dòng)畫整理

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

數(shù)據(jù)結(jié)構(gòu)與算法——堆

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！