小根堆实现

silencezwm 发布于2019-08-14 17:21 / 2764人阅读

摘要：如果有一个关键字的集合把所有元素按完全二叉树的顺序存储方式存放在一个一维数组中，并且满足且向上取整则称这个集合为小根堆。

如果有一个关键字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉树的顺序存储
方式存放在一个一维数组中，并且满足
ki <= k2i+1 且 ki <= k2i+2 (i = 0, 1, ..., (n-2)/2 向上取整)
则称这个集合为小根堆。

创建

复制堆数组

找到最初的调整位置，即最后一个分支结点

自底向上逐步扩大形成堆

向前换一个分支结点

插入

将待插入元素插入已建成堆的最后面

沿着出入位置所在的分支逐步向上调整

删除

将顶元素删除

将数组中最后一个元素放到堆顶

自顶向下调整

代码实现

import java.util.Arrays;

/**
 * Created by mico on 2017/2/5.
 */
public class HeapExam {
    /**
     * 小根堆初始化
     *
     * @param a
     * @param length
     */
    public void minHeap(int a[], int length) {
        for (int i = length >> 1; i >= 0; i--) {
            adjustMinHeap(a, length, i);
        }
    }

    /**
     * 排序 topn
     *
     * @param a
     * @param length
     */
    public void sort(int a[], int length) {
        for (int i = 0, last = length; i < length - 1; i++) {
            swap(a, 0, --last);
            minHeap(a, last);

        }
    }


    /**
     * 小根堆调整
     *
     * @param a
     * @param length
     * @param i
     */
    private void adjustMinHeap(int[] a, int length, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int minIndex = i;
        if (left < length && a[left] < a[i]) {
            minIndex = left;
        }
        if (right < length && a[right] < a[minIndex]) {
            minIndex = right;
        }
        if (minIndex != i) {
            swap(a, i, minIndex);
            adjustMinHeap(a, length, minIndex);
        }

    }


    /**
     * 交换 数组值
     *
     * @param a
     * @param i
     * @param j
     */
    private void swap(int[] a, int i, int j) {
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }


}

测试

public static void main(String[] args) {
        int[] a = {153, 173, 728, 9, 425, 165, 7, 233};
        //int[] arry_int={13, 38, 27, 55, 76, 65, 49, 97};
        HeapExam exam = new HeapExam();
        exam.minHeap(a, a.length);
        System.out.println("小根堆：" + Arrays.toString(a));
        exam.sort(a, a.length);
        System.out.println("排序结果：" + Arrays.toString(a));
    }

输出

小根堆：[7, 9, 153, 173, 425, 165, 728, 233]
排序结果：[728, 425, 233, 173, 165, 153, 9, 7]

超融合服务器服务器托管小根堆 java默认堆实现堆破坏堆碎片

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

转载请注明本文地址：https://www.ucloud.cn/yun/66578.html

七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0
排序算法

摘要：排序代码实现和一概念排序算法的稳定性稳定性稳定排序算法会让原本有相等键值的纪录维持相对次序。交换的结果导致结点的值变化了，重复，，的操作，直到没有孩子时跳出代码实现构建初始堆堆排序算法思想大顶堆举例将待排序的序列构造成一个大顶堆。排序代码实现：Java 和 Python 一、概念 1.1 排序算法的稳定性稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序...

kevin 2019-08-19 10:56 评论0 收藏0
排序算法

摘要：排序代码实现和一概念排序算法的稳定性稳定性稳定排序算法会让原本有相等键值的纪录维持相对次序。交换的结果导致结点的值变化了，重复，，的操作，直到没有孩子时跳出代码实现构建初始堆堆排序算法思想大顶堆举例将待排序的序列构造成一个大顶堆。排序代码实现：Java 和 Python 一、概念 1.1 排序算法的稳定性稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序...

binaryTree 2019-07-31 11:11 评论0 收藏0
2019年京东面试题-洗咖啡杯问题【贪心和动态规划】

摘要：京东年面试题冲咖啡和洗咖啡杯问题题目描述首先，给你几个数据数组表示几个咖啡机，这几个咖啡机生产一杯咖啡所需要的时间就是数组中的值，例如就表示第一台咖啡机生产一杯咖啡需要单位时间，第二台需要单位时间，第三台需要单位时间。 ...

kamushin233 2021-11-16 11:44 评论0 收藏0
常见八大排序详解

摘要：按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。但希尔排序是非稳定排序算法。稳定性分析与直接插入排序不同，希尔排序中的分组插入可能导致顺序移位。所以，插入排序是稳定的排序算法。目录冒泡排序：插入排序希尔排序：堆排序：选择排序快速排序：挖坑法：前...

xfee 2021-11-22 09:34 评论0 收藏0