資訊專欄INFORMATION COLUMN
摘要：思路是從底部開(kāi)始構(gòu)建數(shù)組，將較小的結(jié)點(diǎn)移向上層結(jié)點(diǎn)。交換了和之后，還要重新被交換到末位的原先的，即交換之后的。然后不斷減小，直到整個(gè)數(shù)組完成。其實(shí)，這就相當(dāng)于對(duì)數(shù)組進(jìn)行堆排序。
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].
ClarificationWhat 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.
O(n) time complexity
Note首先，先搞懂幾個(gè)概念：heap，min-heap，complete tree。這里只要知道heap是一種complete tree的樹(shù)結(jié)構(gòu)，結(jié)點(diǎn)i的左右子結(jié)點(diǎn)的index為2*i+1和2*i+2，min-heap是子結(jié)點(diǎn)大于根節(jié)點(diǎn)的樹(shù)，就大概明白題目要怎么heapify了。
思路是從底部開(kāi)始構(gòu)建數(shù)組，將較小的結(jié)點(diǎn)移向上層結(jié)點(diǎn)。先取數(shù)組末尾的兩個(gè)元素為left和right，若2*i+1和2*i+2越界，則賦Integer.MAX_VALUE，這樣可以在后面的分支語(yǔ)句避免對(duì)越界情況不必要的討論。然后，取left和right的較小者和上層A[i]結(jié)點(diǎn)交換，實(shí)現(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不斷減小，直到整個(gè)數(shù)組完成heapify。
其實(shí)，這就相當(dāng)于對(duì)數(shù)組A進(jìn)行堆排序。
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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65749.html
摘要：一個(gè)常見(jiàn)的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序，并將使用實(shí)現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個(gè)一個(gè)堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個(gè)堆。 堆是什么？ 堆是基于樹(shù)抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個(gè)常見(jiàn)的例子就是優(yōu)先隊(duì)列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
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...
摘要：二叉樹(shù)二叉樹(shù)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹(shù)通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成。 二叉樹(shù) 二叉樹(shù)(Binary Tree)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹(shù)通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成。而每個(gè)分支節(jié)點(diǎn)也常常被稱作為一棵子樹(shù)。 showImg(https://segmentfault.com/img/bVbmEd...
摘要：堆排序堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。代碼實(shí)現(xiàn)構(gòu)建堆由下往上構(gòu)建所以用每次踢掉求出的最大值 堆排序 堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)（但是不保證所有左子樹(shù)比右子樹(shù)小反之亦然）。堆排...
摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序歸并排序堆排序獲取個(gè)數(shù)處理一半的數(shù)據(jù) function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...
閱讀 2567·2021-11-22 12:05
閱讀 3453·2021-10-14 09:42
閱讀 1686·2021-07-28 00:15
閱讀 1989·2019-08-30 11:08
閱讀 1487·2019-08-29 17:31
閱讀 932·2019-08-29 16:42
閱讀 2340·2019-08-26 11:55
閱讀 2119·2019-08-26 11:49
