2021-06-26堆

2021-06-28  本文已影响0人  竹blue

概念

  1. 一个完全二叉树
  2. 每个节点的值都必须大于等于[大顶堆](或小于等于[小顶堆])其子树中每个节点的值。
  3. 说明:堆其实就是一种完全二叉树,最常用的存储方式就是数组。[说明:堆中序遍历就是有序的数组]

存储

数组

操作

插入一个元素和删除堆顶元素

堆排序

  1. 借助堆实现的排序算法。
  2. 时间复杂度非常稳定,是O(n*logn)。
  3. 是原地排序算法。

如何基于堆去实现排序?

第一步 建堆

  • 思路1:从前往后处理数组数据,并且每个数据插入堆中时,都从下往上堆化。

  • 思路2:从后往前处理数组,并且每个数据都是从上往下堆化。

    //小顶堆
    PriorityQueue<Integer> small = new PriorityQueue<>();
    //大顶堆
    PriorityQueue<Integer> big = new PriorityQueue<>((x, y) -> (y - x));
    

第二步 排序

  1. 堆顶跟最后一个元素交换,把下标为n的元素放到堆顶,通过堆化的方法,将剩下的n-1个元素重新构建成堆。
  2. 堆化完成之后,取堆顶元素,放到下标是n-1的位置。
  3. 一直重复这个过程,直到最后堆中只剩下标为1的一个元素,排序工作就完成了。

为什么快排比堆排序性能好?

  1. 堆排序数据访问的方式没有快排友好
  2. 同样的数据,在排序过程中,堆排序算法的数据交换次数多于快速排序。

应用

  1. 优先级队列
  2. 针对静态/动态数据集合求Top K
  3. 求动态数据集合中的中位数
上一篇 下一篇

猜你喜欢

热点阅读