1、非线性表之堆

  1. 1、堆(Heap)-概述
  2.     1-1、堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象
  3.     1-2、堆总是一棵完全二叉树。
  5. 2、堆-特性
  6.     2-1、堆中某个节点的值总是不大于或不小于其父节点的值；
  7.     2-2、堆有序的特点，一般用来做数组中的排序，称为堆排序；
  9. 3、堆-属性
  10.     3-1、将根节点最大的堆叫做最大堆或大根堆；
  11.     3-2、根节点最小的堆叫做最小堆或小根堆。
  13. 4、常见的堆有二叉堆、斐波那契堆等。
  15. 5、堆-定义
  16.     5-1、n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
  17.     5-2、小顶堆：(ki <= k2i,ki <= k2i+1) (i = 1,2,3,4…n/2)
  18.     5-3、大顶堆：(ki >= k2i,ki >= k2i+1) (i = 1,2,3,4…n/2)

1.1、大顶堆|小顶堆-示意图

图片.png

1.2、堆排序

  1. 1、堆排序：
  2.     1-1、利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
  3.     1-2、堆是具有以下性质的完全二叉树：
  4.         1-2-1、每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
  5.         1-2-2、或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆(一般升序采用大顶堆，降序采用小顶堆)。
  7. 2、堆排序-举例
  8.     2-1、对堆中的结点按层进行编号，将这种逻辑结构映射到数组中：
  9.     2-2、arr {50,45,40,20,25,35,30,10,15}
  10.     2-3、用公式描述堆的定义则为：
  11.         大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  
  12.         小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  
  14. 3、堆排序的基本思想是：
  15.     3-1、将待排序序列构造成一个大顶堆(一般升序采用大顶堆，降序采用小顶堆)，此时，整个序列的最大值就是堆顶的根节点。
  16.     3-2、<找到非叶子节点> <=> 将其(堆顶元素)与末尾元素进行交换(从左到右,从上到下)，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了