堆排序的进一步理解

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

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

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

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 ; }

转载于:https://www.cnblogs.com/NYNU-ACM/p/4237401.html

总结

以上是生活随笔为你收集整理的堆排序的进一步理解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。