lwz blog

# 堆排序

堆排序是一种树形选择排序，选择最小或最大的元素加入到有序序列中。

# 1. 堆的定义

堆是一种完全二叉树，分为大根堆和小根堆。

# 二叉树的顺序存储

二叉树的顺序存储是将二叉树的节点按照层序遍历的顺序存储到数组中。

下标从1开始，对于任意节点i，有：

  • i的父节点：i/2
  • i的左孩子节点：2i
  • i的右孩子节点：2i+1
  • i的最后一个叶子节点：n/2
  • i所在的层：log2(n+1)或log2n+1

# 大根堆

每个节点的值都大于或等于其左右孩子节点的值。

L(i) <= L(2i+1) && L(i) <= L(2i+2) 1<=i<=n/2

int a=[0,87,45,78,32,17,65,53,09] //存储堆的数组
//变成二叉树就是(逻辑上的)
//          87
//      45      78
//    32  17  65  53
//   09

大根堆的特点：

  1. 根节点的值最大
  2. 根节点的值大于左右孩子节点的值 根>=左 && 根>=右

# 小根堆

每个节点的值都小于或等于其左右孩子节点的值。

L(i) >= L(2i+1) && L(i) >= L(2i+2) 1<=i<=n/2

int a=[0,09,17,32,45,78,65,53,87] //存储堆的数组
//变成二叉树就是(逻辑上的)
//          09
//      17      32
//    45  78  65  53
//   87

小根堆的特点：

  1. 根节点的值最小
  2. 根节点的值小于左右孩子节点的值 根<=左 && 根<=右

# 2. 建立堆

把所有的非终端节点都检查一遍，使其满足堆的性质。如果不满足，就调整。

检查当前节点是否满足堆的性质，如果不满足，将当前节点与更大的一个或者更小的一个孩子节点交换，直到满足堆的性质。

//举例
int a=[0,53,17,78,09,45,65,87,32] //存储堆的数组

//第一次检查 53，17，78，09

//          53
//      17      78
//    09  45  65  87
//   32

// 上述树的非终端节点有4个，分别是53,17,78,09  从后往前查找 也就是 i/2。 09不满足堆的性质，将09与左右孩子中较大的一个交换

//          53
//      17      78
//    32  45  65  87
//   09

# 建立大根堆

int a=[0,53,17,78,09,45,65,87,32] //存储堆的数组

void buildMaxHeap(int a[],int len){
  //从最后一个非终端节点开始，从后往前检查
    for(int i=n/2;i>0;i--){
        heapify(a,i,len);
    }
}

void heapify(int a[],int n,int len){
  a[0]=a[n];  //a[0]暂存当前节点
  for(int i=2*n;i<=len;i*=2){
    if(i<len && a[i]<a[i+1]){ //找到左右孩子中较大的一个
      i++;
    }
    if(a[0]>=a[i]){ //如果当前节点大于左右孩子中较大的一个，不需要交换
      break;
    }else{
      a[n]=a[i]; //否则交换
      n=i; //继续检查
    }
  }

}

# 3. 堆排序(大根堆)

选择排序：每一趟在待排序中选取最大的元素放到有序序列中。

堆排序 每一趟将堆顶元素与堆中最后一个元素交换，然后将剩余的元素重新调整为堆。


void heapSort(int a[],int len){
  buildMaxHeap(a,len); //建立大根堆
  for(int i=len;i>1;i--){
    swap(a[i],a[1]); //交换堆顶元素和堆中最后一个元素
    heapify(a,1,i-1); //重新调整堆
  }
}

不断的建立堆，然后交换堆顶元素和堆中最后一个元素，然后重新调整堆，直到堆中只剩下一个元素。

# 算法分析

# 空间复杂度

O(1)

# 时间复杂度

O(n)+O(nlog2n)=O(nlog2n)

建立堆的时间复杂度为O(n)

# 稳定性

不稳定

← 归并排序 →