排序算法(二)---堆排序2017-11-10 09:23:13

堆排序


    堆排序与插入排序的相同之处在于都具有空间原址性,即只需要常数个额外的元素空间来存储临时数据。它使用一种称为的数据结构来进行信息管理。二叉堆是一个数组(如图所示)

sort2-1.png


它可以被看成是一个近似的完全二叉树,树上的每一个结点对应于数组中的每一个元素。除了最底层外,该树是完全充满的,而且是从左到右填充。这种结构,可以通过一个结点很轻松的得到它的父节点和左孩子和右孩子。

代码如下:

int Parent(int i) {
       return i / 2;
}
int Left(int i) {
       return 2 * i;
}
int Right(int i) {
       return 2 * i + 1;
}


    此处要注意的是在实际的数组中,序号是从开始,若从0开始,则左孩子和右孩子并不符合此规律,所以在实现该算法时要注意处理序号的问题。

    在大多数计算机中,通过将i的值左移一位,Left过程可以在一条指令内完成。类似,Right过程也可以通过将i的值左移一位并在低位加1,也可快速计算得到2i+1Parent过程,可以直接把i的值右移一位计算得到。

    二叉堆可以分为两种形式:最大堆和最小堆。在最大堆中,最大堆的性质是指除了根以外的所有结点都满足: A[Parent(i)]>=A[i],也就是说某个结点的值至多与其父结点一样大。最小堆则相反。在堆排序算法中,我们使用的是最大堆。

维护最大堆

 

代码如下:

void Max_Heapify(int* array, int i, int heapsize) { //树的规律与数组本身的序号有矛盾
       int l, r, largest, temp;
       int treeNum;
       treeNum = i + 1;
       l = Left(treeNum);
       r = right(treeNum);
       if (l <= heapsize&&*(array + l-1) > *(array + i)) {
              largest = l-1;
       }
       else {
              largest = i;
       }
       if (r <= heapsize&&*(array + r-1) > *(array + largest)) {
              largest = r-1;
       }
       if (largest != i) {
              temp = *(array + largest);
              *(array + largest) = *(array + i);
              *(array + i) = temp;
              Max_Heapify(array, largest, heapsize);
       }
}

该算法的参数分别是数组的首地址,要维护最大堆的数组序号,维护堆的大小。

这里要注意处理树的规律与数组本身序号的矛盾。

   该算法的目的很简单,将传入的数组序号作为根节点,然后与它的左孩子和右孩子做对比,若比根节点大,则调换,若都比根结点小,则符合条件,函数执行完毕。

    例如执行函数前

sort2-2.png

执行函数后:

sort2-3.png

构建最大堆

  根据上面的算法,很容易想到如何构建一个最大堆。

代码如下:

void Build_Max_Heap(int* array, int arraysize) {  //建立最大堆 
       for (int i = arraysize / 2; i >= 1; i--) {
              Max_Heapify(array, i-1, arraysize);
       }
}


从树的规律可以看出,构建最大堆可以从数组大小的一半开始,不断执行Max_Heapify 函数,直到该树的根结点,即可得到最大堆。

我们可以想到,构建最大堆后,数组的元素从上至下依次减小,但是不是已经排序好了吗?

这是得到的最大堆:

sort2-4.png

从图中可以看出,我们也可以想到,上述的算法只是比较父结点和子结点的大小,左孩子和右孩子并没有比较过大小,显然我们的排序还未完成。

  从上述图的规律,可以看出即使子结点的大小还未比较,但父结点一定会比子结点要大,所以根结点就会是该数组的最大值。

至此我们的思路也就有了。

代码如下:

int array[10] = { 16,4,10,14,7,9,3,2,8,1 };
       /*----------------------------*/
       //HeapSort
       int temp,heapsize;
       heapsize = 10;
       Build_Max_Heap(array, 10);
       for (int i = 9; i >= 1; i--) {
              temp = array[0];
              array[0] = array[i];
              array[i] = temp;
              heapsize--;
              Max_Heapify(array, 0, heapsize);
       }
       /*----------------------------*/


既然根结点是最大值,所以我们首先构建最大堆,然后将根结点与最末的结点互换位置,同时树的大小同时减一,并且维护序号为1的结点,此时又会得到一个新的根结点,这个结点即是该数组的第二大元素,不断循环这个过程,最后得到的树会是:

sort2-5.png

到这里,该算法就结束了,堆排序的时间复杂度是O(nlgn)。实际上,的这种数据结构不仅可以用以堆排序,也可以构造一种有效的优先队列。这个将会在以后继续进行讨论。



linweiyu

Something should be here;

0 Thoughts

Leave a Thought