首页 > 代码库 > 堆排序的进一步理解

堆排序的进一步理解

2024-07-14 00:33:06   221人阅读

堆-顾名思义，上面小，下面大，或者上面大，下面小。

在堆排序过程中，首先应该建堆。如何将数组中的元素建立成一个规范的堆行结构。

二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

假设根结点的下标为1，则第 i 个结点的父结点下标为 i / 2 ， 第 i 个结点的左子结点的下标为2*i, 右子结点的下标为2*i+1 ;

如何才能使得数组中元素形成堆的结构呢？首先将父结点、左子结点、右子结点这三个结点看成一个小堆或者一个小三角形，叶子结点无左子结点和右子结点，所以默认叶子结点为堆结构。则最后一个元素的父结点下标为 i/2， 从 i/2 开始，直到根结点为止，小三角形的面积逐渐增大，到根结点时达到最大，也就完成了堆的建立。

接下来进行的是堆排序操作，由于根结点元素为最大元素，每次先将根结点元素和最后一个元素调换，然后再调整堆即可，直到堆中元素只剩一个时结束，这样数组中的元素就为有序的元素。具体代码如下：

#include<stdio.h>void MaxHeap(int a[] ,  int i , int n)  {        int j ;        a[0] = a[i] ;        j  = 2 * i ;        while ( j <= n )        {                if(j + 1 <= n && a[j + 1] > a[j])                        j++ ;                if(a[0] >= a[j])                        break ;                a[i] = a[j] ;                i = j ;                j = 2 * i ;        }        a[i] = a[0] ;}void MakeMaxheap(int a[] ,  int n )     {        int i ;        for(i = n / 2 ; i >= 1 ; i--)                MaxHeap(a,i,n) ;}void swap(int &a , int &b)      {        int t = a ;        a = b ;        b = t ;}void Delete(int a[] ,  int n )  {        swap(a[1],a[n]) ;//      printf("%d\n",a[1]) ;        MaxHeap(a,1,n-1) ;}int main()      {        int a[] = {0,16,4,10,14,7,9,3,2,8,1} ;        MakeMaxheap(a,10) ;        int i ;        for(i = 1 ; i < 11 ; i++)                printf("%d ",a[i]) ;        printf("\n") ;        return 0 ;}


联系
我们