神刀安全网

堆排序

堆排序

堆排序的核心思想:借助堆数据结构,不断输出当前堆顶元素,每次堆顶离开当前堆后,对剩余元素重新调整成堆,直到堆中只剩下一个元素;元素的输出序列可转换成元素的有序序列

思路:

1、 我们以最大堆为例,在原数组上把元素按从小到大排序

2、 我们先对无序的数组初始化;即调整成最大堆;

2.1、无序的数组初始化最大堆思路:假设堆从root到叶子下标从0开始,它有一个性质:即int i = (叶子的节点下标/2) 得到第一个子树,我们把它向下调整成最大堆,然后i–,把以i为下标的子树调整成最大堆…直到root

3、交换arr[0]和arr[length – 1] , 把剩余的元素调整成最大堆

4、(length-1)– ; 循环调用步骤3-4,直到还剩下一个元素

向下调整思路:
前提:堆结构中,只有要调整的那个元素,不满足最大堆结构 

1、 以下图为例,index = 0(要调整的元素) ,我们先确定它是否有左孩子,有左孩子则继续;否则退出

2、 我们把要调整的元素和两个孩子中最大的那个比较,如果要调整的元素值大,则返回;否则交换要调整的元素和子孩子中大的那一个,更新index;循环调用1-2

堆排序

请看图

好了,知道了思路我们来实现一下

void heapSort(int arr[] , int length ){     //1、先调成最大堆     for(int i = (length - 1) / 2; i >= 0 ; i--){         _shiftDown(arr , length , i);     }     //2、堆排序     for(int i = length - 1 ; i > 0 ; i--){         swap(arr[i] , arr[0]);         _shiftDown(arr , i , 0);     }  } 

向下调整

void _shiftDown(int arr[] , int length , int index){     //要确保以index为根的完全二叉树有左孩子才能向下调整     while( 2 * index + 1 < length ){         int j = 2 * index + 1;                  //因为是最大堆,我们要和子孩子中最大的一个交换值         if(j + 1 < length && arr[j + 1] > arr[j]){             j = j + 1;         }                 //如果最大的子孩子不大于它的父亲的值,则终止循环         if(arr[index] >= arr[j]){             break;         }         //否则,交换值,更新下标,继续向下调整         swap(arr[index] , arr[j]);         index = j;     }  } 

注:
1、因为堆的结构是完全二叉树,因此可以用数组的结构来存储(看图)

2、初始化数组时,为什么不直接从root开始?
因为我们不能保证root的左右两个子树满足最大堆结构,堆排序的前提:堆结构中,只有要调整的那个元素,不满足最大堆结构

3、 为什么向下调整用while循环,因为我们也不知道循环多少次
4、 swap函数是c++自带的

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 堆排序

分享到:更多 ()