[LintCode] Heapify

denson 發布于2019-08-14 15:25 / 2424人閱讀

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

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的樹結構，結點i的左右子結點的index為2*i+1和2*i+2，min-heap是子結點大于根節點的樹，就大概明白題目要怎么heapify了。
思路是從底部開始構建數組，將較小的結點移向上層結點。先取數組末尾的兩個元素為left和right，若2*i+1和2*i+2越界，則賦Integer.MAX_VALUE，這樣可以在后面的分支語句避免對越界情況不必要的討論。然后，取left和right的較小者和上層A[i]結點交換，實現min-heap結構。交換了A[i]和A[2*i+1]/A[2*i+2]之后，還要重新heapify被交換到末位的原先的A[i]，即交換之后的A[2*i+1]/A[2*i+2]。然后i不斷減小，直到整個數組完成heapify。
其實，這就相當于對數組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);
        }
    }
}

GPU云服務器云服務器 Heapify LintCode LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65749.html

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

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

twohappy 2019-07-01 10:32 評論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...

陳江龍 2019-08-14 18:40 評論0 收藏0
js數據結構-二叉樹（二叉堆）

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

ningwang 2019-08-23 14:29 評論0 收藏0
python 堆排序

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

genedna 2019-07-31 11:18 評論0 收藏0
php插入排序,快速排序,歸并排序,堆排序

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

JerryZou 2019-07-01 10:12 評論0 收藏0