首页 > 代码库 > 排序之堆排序

排序之堆排序

2024-07-19 05:49:46   223人阅读

一、什么是堆？

　　1. 定义：二叉堆数据结构是一种数组对象，它通常可视为一棵完全二叉树。这样讲估计比较抽象，来看下它的逻辑定义：有一个包含n个元素的数组A[n]={k1,k2...ki...kn}，当且仅当满足下列关系时称之为堆：
　　(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)。

通俗来讲，即一个数组中的元素之间存在如上的关系，就是一个堆。

　　2. 二叉堆的分类

　　二叉堆有两种：最大堆和最小堆。在最大堆中，最大堆特性是指对于每个结点i，都有父结点的值大于等于其所有子结点的值；反之，在最小堆中，父结点的值应小于等于子结点的值。

　　根据最大堆和最小堆的定义，可从中发现：在最大堆中，根结点为所有结点中值最大的点，最小堆中根结点为所有结点中值最小的点。在堆排序算法中，一般使用最大堆，最小堆通常在构造优先队列时使用。

 

二、建立堆

　　在堆排序算法中，首先需要将一个乱序的数组建成一个堆，然后在堆的基础上进行排序。我们以待排序数组A[7] = {1,3,4,6,2,9,7}为例，将其建成一个最大堆。我们以完全二叉树的形式将整个过程表示出来，应该会更加直观。

　　数组的初始状态（圈外编号为该结点在数组中所处的下标，圈内值为该结点的值）：

　　观察这个完全二叉树，要使这个完全二叉树的每个父结点都要大于或等于其所有子结点，我们该从哪个结点开始入手呢？乍一看，感觉有种触一发而动全身的感觉，无从下手啊！在此，可借鉴算法中常用的一种思想，先局部在整体。要使整个二叉树满足条件最大堆的条件，那么就必须使该树中的任意子树都要满足这个条件。我们以下面这个子树为例：

父结点的值为1，小于其所有子结点，因此，需要将其与子结点置换。可以发现，结点1和2的值都要大于1，那么置换哪个结点呢？当然置换值较大的那个啦，不然将值小的置换上去依然不能满足堆的条件啊！置换完后二叉树变为：

大家可以发现，置换之后又出现了情况，虚线区域内的子树不满足最大堆的要求，那么就得按照上面的要求再对该子树进行置换。

到此，是不是有点感觉了？这是不是有点递归的意思了？看下代码：

  1. /**
  2.  * 针对一个结点操作
  3.  * @param A[] 完全二叉树
  4.  * @param i 当前结点
  5.  * @param size 结点总数
  6.  */
  7. void heapify(int A[], int i, int size) {
  8.     if(i>=size) { //判断i是否合法
  9.         return;
  10.     } else {
  11.         int left = i*2+1; //左子结点编号（根节点编号为0）
  12.         int right = i*2+2; //右子结点编号
  13.         int largest = i; //默认当前父结点为最大
  14.         if(left<size) {
  15.             if(A[largest]<A[left]) {
  16.                 largest = left;
  17.             }
  18.         }
  19.         if(right<size) {
  20.             if(A[largest]<A[right]) {
  21.                 largest = right;
  22.             }
  23.         }
  24.         if(largest!=i) { //将最大值换到父结点
  25.             int temp = A[i];
  26.             A[i] = A[largest];
  27.             A[largest] = temp;
  28.             heapify(A, largest, size);
  29.         }
  30.     }
  31. }

　　上面的代码主要解决针对的是树中的一个结点，对于整个树，则需要遍历树中的每个结点（一般自底向上），代码如下：

  1. /**
  2.  * 对所有结点
  3.  * @param A[] 完全二叉树
  4.  * @param size 结点总数
  5.  */
  6. void max_heapify(int A[], int size) {
  7.     int i;
  8.     for(i=size-1; i>=0; i--) {//从下往上
  9.         heapify(A, i, size);
  10.     }
  11. }

　　这样，整个最大堆就建好了！

　　为了更加清楚的表示这个过程，还是用二叉树表示下吧！

　　步骤一：根据代码可知，从底向上（从数组的角度看，是从数组的尾部向首部移动），即从结点6开始。由于其没有子结点，因此不做任何操作。以此类推，实际的工作从结点2开始，显而易见，结点2需要和其子结点置换。

　　步骤二：遍历到结点1，依然需要置换。

　　步骤三：遍历到结点0，依然需要置换。

　　步骤四：由于结点2的值发生了改变，需要查看该子树，发现需要置换。

　　此时，发现没有需要置换的结点，最大堆建造完毕！

 

二、堆排序

　　堆建好之后，对堆进行从小到大的排序就变得很简单了。第一次建堆之后，数组中元素变为：

每次建堆之后，数组中元素0都为最大值，因此，将元素0和元素6对调，则数组变为：

此时，元素0~5组成的数组不是最大堆，则重新对这六个元素建堆，又得到这六个元素中的最大值，将元素0与元素5对调，以此类推，直到只剩一个元素建堆，即可得到一个从小到大的有序数组。代码如下：

 

  1. /**
  2.  * 对堆排序
  3.  * @param A[] 完全二叉树
  4.  * @param size 节点总数
  5.  */
  6. void heap_sort(int A[], int size) {
  7.     int i;
  8.     for(i=size-1; i>=0; i--) {
  9.         max_heapify(A,i+1);
  10.         int temp = A[i];
  11.         A[i] = A[0];
  12.         A[0] = temp;
  13.     }
  14. }

　　测试方法：

  1. int main()
  2. {
  3.     int A[7] = {1,3,4,6,2,9,7};
  4.     heap_sort(A,7);
  5.     int i;
  6.     for(i=0; i<7; i++) {
  7.         printf("%d",A[i]);
  8.     }
  9.     return 0;
  10. }

 

　　

 

排序之堆排序


联系
我们