[LintCode] Heapify

denson 发布于2019-08-14 15:25 / 2396人阅读

摘要：思路是从底部开始构建数组，将较小的结点移向上层结点。交换了和之后，还要重新被交换到末位的原先的，即交换之后的。然后不断减小，直到整个数组完成。其实，这就相当于对数组进行堆排序。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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