博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构与算法-学习笔记(20)
阅读量:6194 次
发布时间:2019-06-21

本文共 1383 字,大约阅读时间需要 4 分钟。

什么是堆?

① 对是一个完全二叉树 ; ② 堆中的每个节点的值都必须 >=(或者<=)其子树中每个节点。

如何实现一个堆

  1. 如何存储一个堆:完全二叉树,用数组最好了。

2. 插入

插入完全二叉树中,也就是插入到数组的最后一个位置。

此时破坏了堆的特性,需要调整(也叫堆化):

① 从下往上 比较交换直到符合规则

② 从上往下比较交换直到符合规则

  1. 删除

堆的插入删除操作都是顺着节点路径比较交换,完全二叉树的高度log2n,因此时间复杂度O(logn)

堆排序

借助堆结构的特点,把数组中数据位置对应到堆上对应位置,通过调整堆来对数组中数据进行排序。

对一组数据进行堆排序(以大顶堆为例)。

  1. 一组数据可以对应成一个完全二叉树。
  2. 对完全二叉树进行调整(也就是堆化)成堆。这一步类似插入操作,插入后的数据最终是在叶子节点上的。因此从最后一个节点开始从上往下进行堆化。节点n是叶子节点没有子节点因此从他的父节点开始。
private static void buildHeap(int[] a, int n) {  for (int i = n/2; i >= 1; --i) {// 它是完全二叉树,因此有子节点的父节点i向上肯定都是父节点    heapify(a, n, i);  }}private static void heapify(int[] a, int n, int i) {  while (true) { // 交换后节点下边的子树又需要重新刷新位置    int maxPos = i;    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;    if (maxPos == i) break;    swap(a, i, maxPos);    i = maxPos;  }}复制代码
  1. 排序 大顶堆已经排序好了,现在堆顶的元素肯定是数组中最大值,因为要原地排序且不能破坏堆的结构因此将堆顶元素与尾节点交换(类似删除操作),之后对新顶节点进行自上向下堆化(堆的范围1~n-1),完成后,堆顶又是最大元素。以此类推,每次将堆顶拿出,也就是每次找到剩余元素的最大值。重复n次所有元素就都排好了。
// n 表示数据的个数,数组 a 中的数据从下标 1 到 n 的位置。public static void sort(int[] a, int n) {  buildHeap(a, n);  int k = n;  while (k > 1) {    swap(a, 1, k);    --k;    heapify(a, k, 1);  }}复制代码

堆排序的测评

空间复杂度O(n)

时间复杂度O(nlogn)

不稳定排序

为什么实际开发中快速排序好于堆排序?

  1. 堆排序数据访问方式没有快速排序友好:快:顺序(CPU缓存友好);堆:跳着
  2. 对于同样数据,在排序过程中,堆排序算法的数据交换次数多于快排。

应用

堆的排序过程中,每次都会找出剩余元素中最大的元素,因此可以应用于求topN

转载于:https://juejin.im/post/5c0a47cc6fb9a049b5069fc1

你可能感兴趣的文章
Vue with TypeScript
查看>>
理解闭包
查看>>
减治法-插入排序
查看>>
初尝node.js + Express + MongoDB 项目构建(1)
查看>>
UIViewController和UIView不同加载方式的生命周期函数
查看>>
【php】Mac下从零搭建和配置 php+nginx+mysql 环境
查看>>
iOS 强引用
查看>>
React Native填坑之旅--与Android模块通信
查看>>
新年第一发--深入不浅出zepto的Tap击穿问题
查看>>
webpack 多页面构建
查看>>
原生JavaScript校验身份证号是否正确
查看>>
ES6新语法疑点简析
查看>>
css三栏布局:左右固定宽中间自适应
查看>>
Git 2.19 对Diff、Branch和Grep等做了改进
查看>>
什么是即时编译(JIT)!?OpenJDK HotSpot VM剖析
查看>>
与《管理幸福》一书作者Jurgen Appelo的访谈
查看>>
敏捷和架构设计分道而行,又最终拥抱彼此成为朋友
查看>>
阿里云Redis开发规范
查看>>
独家揭秘:微博深度学习平台如何支撑4亿用户愉快吃瓜?
查看>>
独家!阿里开源自用OpenJDK版本,Java社区迎来中国力量
查看>>