【数据结构】堆排序

大家好，���是苏貝，本篇博客带大家了解堆排序，如果你觉得我写的还不错的话，可以给我一个赞吗，感谢❤️

目录

• 一. 堆的概念
• 二. 堆排序（以升序为例）
• 三. 代码

  一. 堆的概念

  如果有一个关键码的集合K，把它的所有元素按 完全二叉树 的顺序存储方式存储在一个一维数组中，并满足：任意一个双亲结点的值=孩子节点的值），则称为小堆(或大堆)。堆排序即利用堆的思想来进行排序

  ---

  二. 堆排序（以升序为例）

  思路:

  1.将待排序的数组构成一个大堆，此时堆顶元素就是最大的

  2.将堆顶元素与最后一个元素交换，此时最后一个元素就是最大值

  3.删除最后一个元素（实际上没有删除，只是不再和其它元素一起构成大堆），让其它元素再次构成大堆

  4.重复第2、3步：将堆顶元素与最后一个元素（其实是倒数第二个）交换，此时它就是最大值（其实是次大值）……

  1

  为什么不用小堆？

  因为小堆只能保证孩子节点的值>=双亲结点的值，不能保证兄弟节点也是按升序排列的，如：

  从上面我们可以看出，该数组最后并不是升序排列的，因此我们不能构建小堆

  2

  如何构建大堆？

  【数据结构】实现堆

  在上篇博客中，我们在实现堆时，在插入函数中用了向上调整的方法，在这里我们同样也可以采用向上调整的方法。插入第二个元素判断位置是否合适，如果该节点的值>双亲结点的值就向上调整，调整结束后，再插入并判断第三个元素是否合适……循环结束，大堆也就构建好了。

  //void AdjustUp(int* a, int child)//{//int parent = (child - 1) / 2;//while (child > 0)//{//if (a[child] > a[parent])//{//swap(&a[child], &a[parent]);//child = parent;//parent = (child - 1) / 2;//}//else//{//break;//}//}//}for (int i = 1; i  
  3
  将堆顶元素与最后一个元素交换，然后删除最后一个元素（实际上没有删除）
    
  //void AdjustDown(int* a, int size, int parent)//{//int child = parent * 2 + 1;//while (child  a[child])//{//child++;//}//if (a[parent]  0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
   
  4
  建大堆的另一种思路
   
  上面的2利用了插入思想，从第二个元素插入开始判断位置是否合适，不合适就向上调整，调整结束后，再插入并判断第三个元素是否合适……也就是说，在再次插入元素之前，所有的元素已经构成了大堆，插入元素后，再次调整直到为大堆。那如果我一次性插入所有的元素，此时双亲结点和孩子节点没有任何关系，是否还有方法能建成大堆呢？
  从第一个非叶子节点开始，不断向前移动，直到到根节点，每个节点都向下调整。i = (n - 1 - 1) / 2中，n-1是最后一个节点的索引，（孩子节点-1）/ 2==双亲结点的索引
   
  for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
   
  5
  向上和向下调整建堆的时间复杂度
     
  因为向上调整的时间复杂度为O(N*logN)，向下调整的时间复杂度为O(N)，所以向下调整的方法（上面的4）更好。
   
  三. 代码
   
  #include#include#includevoid swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}void AdjustUp(int* a, int child){int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int* a, int size, int parent){int child = parent * 2 + 1;while (child  a[child]){child++;}if (a[parent] = 0; i--){AdjustDown(a, n, i);}//2.排序int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}}int main(){int a[] = { 2,4,3,1,9,6,7,8 };int n = sizeof(a) / sizeof(int);HeapSort(a, n);for (int i = 0; i   
  好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞吗，感谢看到这里，我们下篇博客见❤️