成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

hankkin / 3143人閱讀

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

1. 什么是堆

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

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

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

對于堆中的每個節(jié)點都大于等于其左右子節(jié)點的值，叫做大頂堆，反之，則叫做小頂堆?？纯聪旅娴膱D就能懂了。

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

2. 堆是如何存儲的？

其實，堆可以按照完全二叉樹的存儲方式來儲存，因為完全二叉樹是比較省空間的，所以我們可以直接用數(shù)組來存儲，然后按照數(shù)組下標來取出堆中數(shù)據(jù)。參照下圖，來看看堆的存儲：

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

3. 堆的幾種操作

明白了堆是怎樣儲存的，我們在來看看堆最常見的兩個操作：往堆中插入元素和刪除堆頂元素。

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

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

public class Heap {
    private int[] data;//存儲堆數(shù)據(jù)的數(shù)組
    private int n;//堆中可存儲的元素容量
    private int size;//堆中存儲的元素個數(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é)點 data[(i - 1) / 2] 的值
            swap(data, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
        size ++;
    }
    
    //交換數(shù)組兩個位置的元素
    private void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

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

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

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

    //刪除數(shù)據(jù)，如果是大頂堆，則刪除的是堆中的最大元素
    //如果是小頂堆，則刪除的堆中的最小元素
    public int removeMax(){
        if (size == 0) return -1;//堆為空
        //將數(shù)組中的最后一個元素，放到第一個位置
        int result = data[0];
        data[0] = data[size - 1];
        data[-- this.size] = 0;
        //進行堆化
        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)是怎么實現(xiàn)排序功能的。堆排序的時間復(fù)雜度非常的穩(wěn)定，是O(nlogn)，并且是原地排序算法，具體是怎么實現(xiàn)的呢？我們一般把堆排序分為兩個步驟：建堆和排序。

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

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

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

排序
排序的過程類似于上面說到的刪除堆頂元素，因為堆頂元素是堆的最大或最小元素，以大頂堆為例，我們只需要將堆頂元素和數(shù)組中最后一個元素交換位置，然后重新構(gòu)造堆，繼續(xù)交換堆頂元素和數(shù)組中最后一個未排序數(shù)據(jù)，知道堆中元素剩下最后一個。

示意圖如下：

整個建堆和排序的實現(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é)點依次堆化
    private void buildHeap(int[] data){
        int length = data.length;
        for (int i = (length - 2) / 2; i >= 0; -- i) {
            heapify(data, length, i);
        }
    }

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/74035.html

相關(guān)文章

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

    摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復(fù)雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...

    haitiancoder 評論0 收藏0

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

    摘要：二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊列和著名的堆排序算法中。 二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應(yīng)用于優(yōu)先隊列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個特性： 是一顆完全二叉樹，表示數(shù)的每一層都有左側(cè)和右側(cè)子節(jié)點（除最后一層的葉節(jié)點），并且最后一層的葉節(jié)點盡可能是左側(cè)子節(jié)點 二叉堆不是最小堆就是...

    MartinHan 評論0 收藏0

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

    摘要：前面介紹了七大算法的思想與實現(xiàn)步驟，下面來做一個歸總。直到無序區(qū)中的數(shù)為零，結(jié)束排序。步驟以從小到大為例，排序數(shù)組大小為。比較完以后則排序結(jié)束。堆排序思想堆排序是采用樹的形式的數(shù)據(jù)結(jié)構(gòu)來進行排序的，其中每一個堆都是完全二叉樹。 前面介紹了七大算法的思想與實現(xiàn)步驟，下面來做一個歸總。 排序方法 平均復(fù)雜度 最壞復(fù)雜度 最好復(fù)雜度 輔助空間 穩(wěn)定性 直接選擇排序 O(n^2...

    cartoon 評論0 收藏0

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

    摘要：一虛擬機內(nèi)存圖解程序運行與虛擬機之上，運行時需要內(nèi)存空間。是一種數(shù)據(jù)結(jié)構(gòu)，是虛擬機中的局部變量表，對應(yīng)物理層之上的程序數(shù)據(jù)模型。 一：虛擬機內(nèi)存圖解 JAVA 程序運行與虛擬機之上，運行時需要內(nèi)存空間。虛擬機執(zhí)行 JAVA 程序的過程中會把它管理的內(nèi)存劃分為不同的數(shù)據(jù)區(qū)域方便管理。 虛擬機管理內(nèi)存數(shù)據(jù)區(qū)域劃分如下圖： showImg(https://segmentfault.com/i...

    Jinkey 評論0 收藏0

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

    摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...

    zsy888 評論0 收藏0

發(fā)表評論

0條評論

hankkin

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<