亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LintCode] Heapify

denson / 2468人閱讀

摘要：思路是從底部開始構(gòu)建數(shù)組，將較小的結(jié)點移向上層結(jié)點。交換了和之后，還要重新被交換到末位的原先的，即交換之后的。然后不斷減小，直到整個數(shù)組完成。其實，這就相當(dāng)于對數(shù)組進行堆排序。

Problem

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Clarification

What is heap?
Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.

What is heapify?
Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].

What if there is a lot of solutions?
Return any of them.
Example
Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Note

首先，先搞懂幾個概念：heap，min-heap，complete tree。這里只要知道heap是一種complete tree的樹結(jié)構(gòu)，結(jié)點i的左右子結(jié)點的index為2*i+1和2*i+2，min-heap是子結(jié)點大于根節(jié)點的樹，就大概明白題目要怎么heapify了。
思路是從底部開始構(gòu)建數(shù)組，將較小的結(jié)點移向上層結(jié)點。先取數(shù)組末尾的兩個元素為left和right，若2*i+1和2*i+2越界，則賦Integer.MAX_VALUE，這樣可以在后面的分支語句避免對越界情況不必要的討論。然后，取left和right的較小者和上層A[i]結(jié)點交換，實現(xiàn)min-heap結(jié)構(gòu)。交換了A[i]和A[2*i+1]/A[2*i+2]之后，還要重新heapify被交換到末位的原先的A[i]，即交換之后的A[2*i+1]/A[2*i+2]。然后i不斷減小，直到整個數(shù)組完成heapify。
其實，這就相當(dāng)于對數(shù)組A進行堆排序。

Arrays.sort(A);
Solution 
public class Solution {
    public void heapify(int[] A) {
        for (int i = A.length/2; i >= 0; i--) {
            helper(A, i);
        }
    }
    public void helper(int[] A, int i) {
        if (i > A.length) return;
        int left = 2*i+1 < A.length ? A[2*i+1] : Integer.MAX_VALUE;
        int right = 2*i+2 < A.length ? A[2*i+2] : Integer.MAX_VALUE;
        if (left < right && left < A[i]) {
            A[2*i+1] = A[i];
            A[i] = left;
            helper(A, 2*i+1);
        }
        else if (right < A[i]) {
            A[2*i+2] = A[i];
            A[i] = right;
            helper(A, 2*i+2);
        }
    }
}

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

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

相關(guān)文章

  • PHP面試：說下什么是堆和堆排序？

    摘要：一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序，并將使用實現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個堆。 堆是什么？ 堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...

    twohappy 評論0 收藏0

  • Java - Sorting Algorithms

    Complexity Quicksort Mergesort Heapsort Time Complexity O(nlogn) O(nlogn) O(nlogn) Space Complexity O(1) O(n) Could be O(1) Quicksort Quicksort is s...

    陳江龍 評論0 收藏0

  • js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉堆）

    摘要：二叉樹二叉樹是一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點，分支節(jié)點，葉子節(jié)點組成。 二叉樹 二叉樹(Binary Tree)是一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點，分支節(jié)點，葉子節(jié)點組成。而每個分支節(jié)點也常常被稱作為一棵子樹。 showImg(https://segmentfault.com/img/bVbmEd...

    ningwang 評論0 收藏0

  • python 堆排序

    摘要：堆排序堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆排序可以說是一種利用堆的概念來排序的選擇排序。代碼實現(xiàn)構(gòu)建堆由下往上構(gòu)建所以用每次踢掉求出的最大值 堆排序 堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點（但是不保證所有左子樹比右子樹小反之亦然）。堆排...

    genedna 評論0 收藏0

  • php插入排序,快速排序,歸并排序,堆排序

    摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序歸并排序堆排序獲取個數(shù)處理一半的數(shù)據(jù) function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...

    JerryZou 評論0 收藏0

發(fā)表評論

0條評論

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