堆排序
2019-08-23 本文已影响0人
_Cappuccino_
综述
堆排序是指利用堆这种数据结构所设计的一种排序算法.
堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于（或者大于）它的父节点.
算法描述
1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
2.将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
3.由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn).
4.不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成.
示意图
堆排序动态示意图
详解示意图(感谢https://blog.csdn.net/l577217/article/details/80516654)
性质
排序类别:非交换排序
是否是稳定排序:稳定
是否是原地排序:是
时间复杂度:O(n*log N)
空间复杂度:O(n)
##############################################################
说明
完全二叉树: 除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐.
满二叉树:除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充.
完满二叉树:除了叶子结点之外的每一个结点都有两个孩子结点.
分类
每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.
堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法
最大堆要求节点的元素都要不小于其孩子,最小堆要求节点元素都不大于其左右孩子
那么处于最大堆的根节点的元素一定是这个堆中的最大值
堆排序可以说是一种利用堆的概念来排序的选择排序.
分为两种方法:
大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
Python实现
# 大顶堆进行升序排序
def max_heapify(heap, heapSize, root): # 调整列表中的元素并保证以root为根的堆是一个大根堆
left = 2 * root + 1
right = left + 1
larger = root
print('left:', left, ', right:', right, ', root:', larger)
# 交换的只是下标，完成之后进行数值交换
if left < heapSize and heap[larger] < heap[left]:
larger = left
if right < heapSize and heap[larger] < heap[right]:
larger = right
if larger != root: # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
heap[larger], heap[root] = heap[root], heap[larger]
# 递归的对子树做调整
max_heapify(heap, heapSize, larger)
print(heap)
def build_max_heap(heap): # 构造一个堆，将堆中所有数据重新排序
heapSize = len(heap)
# 构建堆由下往上构建所以用-1
for i in range((heapSize - 2) // 2, -1, -1): # 自底向上建堆
max_heapify(heap, heapSize, i)
def heap_sort1(heap):
# 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
build_max_heap(heap)
print('第一次构建堆完成...')
# 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
for i in range(len(heap) - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
max_heapify(heap, i, 0)
dest1 = [1, 2, 3, 4, 5, 6, 7]
dest2 = [1, 2, 3, 4, 5, 6, 7, 8]
dest3 = [7, 6, 5, 4, 3, 2, 1]
dest4 = [8, 7, 6, 5, 4, 3, 2, 1]
result = heap_sort1(dest1)
print('最后的结果是:', dest1)
print('*' * 50)
result = heap_sort1(dest2)
print('最后的结果是:', dest2)
print('*' * 50)
result = heap_sort1(dest3)
print('最后的结果是:', dest3)
print('*' * 50)
result = heap_sort1(dest4)
print('最后的结果是:', dest4)
print('*' * 50)
'''
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
**************************************************
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
**************************************************
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
**************************************************
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
**************************************************
'''
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = heap_sort1(dest)
print('最后的结果是:', dest)
'''
left: 7 , right: 8 , root: 3
[5, 2, 7, 4, 8, 1, 6, 3]
left: 5 , right: 6 , root: 2
[5, 2, 7, 4, 8, 1, 6, 3]
left: 3 , right: 4 , root: 1
left: 9 , right: 10 , root: 4
[5, 8, 7, 4, 2, 1, 6, 3]
[5, 8, 7, 4, 2, 1, 6, 3]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
[8, 5, 7, 4, 2, 1, 6, 3]
[8, 5, 7, 4, 2, 1, 6, 3]
第一次构建堆完成...
left: 1 , right: 2 , root: 0
left: 5 , right: 6 , root: 2
left: 13 , right: 14 , root: 6
[7, 5, 6, 4, 2, 1, 3, 8]
[7, 5, 6, 4, 2, 1, 3, 8]
[7, 5, 6, 4, 2, 1, 3, 8]
left: 1 , right: 2 , root: 0
left: 5 , right: 6 , root: 2
[6, 5, 3, 4, 2, 1, 7, 8]
[6, 5, 3, 4, 2, 1, 7, 8]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
left: 7 , right: 8 , root: 3
[5, 4, 3, 1, 2, 6, 7, 8]
[5, 4, 3, 1, 2, 6, 7, 8]
[5, 4, 3, 1, 2, 6, 7, 8]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
[4, 2, 3, 1, 5, 6, 7, 8]
[4, 2, 3, 1, 5, 6, 7, 8]
left: 1 , right: 2 , root: 0
left: 5 , right: 6 , root: 2
[3, 2, 1, 4, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
[2, 1, 3, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
left: 1 , right: 2 , root: 0
[1, 2, 3, 4, 5, 6, 7, 8]
left: 1 , right: 2 , root: 0
[1, 2, 3, 4, 5, 6, 7, 8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''
# 小顶堆实现降序排序
def small_heapify(heap, heapSize, root): # 调整列表中的元素并保证以root为根的堆是一个大根堆
left = 2 * root + 1
right = left + 1
small = root
print('left:', left, ', right:', right, ', root:', small)
# 交换的只是下标，完成之后进行数值交换
if left < heapSize and heap[small] > heap[left]:
small = left
if right < heapSize and heap[small] > heap[right]:
small = right
if small != root: # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
heap[small], heap[root] = heap[root], heap[small]
# 递归的对子树做调整
small_heapify(heap, heapSize, small)
print(heap)
def build_small_heap(heap): # 构造一个堆，将堆中所有数据重新排序
heapSize = len(heap)
# 构建堆由下往上构建所以用-1
for i in range((heapSize - 2) // 2, -1, -1): # 自底向上建堆
small_heapify(heap, heapSize, i)
def heap_sort2(heap):
# 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
build_small_heap(heap)
print('第一次构建堆完成...')
# 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
for i in range(len(heap) - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
small_heapify(heap, i, 0)
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = heap_sort2(dest)
print('最后的结果是:', dest)
'''
left: 7 , right: 8 , root: 3
left: 15 , right: 16 , root: 7
[5, 2, 7, 3, 8, 1, 6, 4]
[5, 2, 7, 3, 8, 1, 6, 4]
left: 5 , right: 6 , root: 2
left: 11 , right: 12 , root: 5
[5, 2, 1, 3, 8, 7, 6, 4]
[5, 2, 1, 3, 8, 7, 6, 4]
left: 3 , right: 4 , root: 1
[5, 2, 1, 3, 8, 7, 6, 4]
left: 1 , right: 2 , root: 0
left: 5 , right: 6 , root: 2
[1, 2, 5, 3, 8, 7, 6, 4]
[1, 2, 5, 3, 8, 7, 6, 4]
第一次构建堆完成...
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
left: 7 , right: 8 , root: 3
[2, 3, 5, 4, 8, 7, 6, 1]
[2, 3, 5, 4, 8, 7, 6, 1]
[2, 3, 5, 4, 8, 7, 6, 1]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
left: 7 , right: 8 , root: 3
[3, 4, 5, 6, 8, 7, 2, 1]
[3, 4, 5, 6, 8, 7, 2, 1]
[3, 4, 5, 6, 8, 7, 2, 1]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
left: 7 , right: 8 , root: 3
[4, 6, 5, 7, 8, 3, 2, 1]
[4, 6, 5, 7, 8, 3, 2, 1]
[4, 6, 5, 7, 8, 3, 2, 1]
left: 1 , right: 2 , root: 0
left: 5 , right: 6 , root: 2
[5, 6, 8, 7, 4, 3, 2, 1]
[5, 6, 8, 7, 4, 3, 2, 1]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
[6, 7, 8, 5, 4, 3, 2, 1]
[6, 7, 8, 5, 4, 3, 2, 1]
left: 1 , right: 2 , root: 0
left: 3 , right: 4 , root: 1
[7, 8, 6, 5, 4, 3, 2, 1]
[7, 8, 6, 5, 4, 3, 2, 1]
left: 1 , right: 2 , root: 0
[8, 7, 6, 5, 4, 3, 2, 1]
left: 1 , right: 2 , root: 0
[8, 7, 6, 5, 4, 3, 2, 1]
最后的结果是: [8, 7, 6, 5, 4, 3, 2, 1]
'''
# 非递归实现堆排序
def heapAdjust(arr, start, end):
i = start
temp = arr[start]
j = 2 * i
while j <= end:
if j < end and arr[j] < arr[j + 1]:
j += 1
if arr[i] < arr[j]:
arr[i] = arr[j]
i = j
j = 2 * i
else:
break
arr[i] = temp
print(arr)
def heap_sort3(numList):
# 由于python数组的下标从0开始，因此需要加入一个辅助元素，是所有的元素的下标都往后移动一位。
numList.insert(0, 0)
length = len(numList) - 1
firstAdjustRoot = length // 2
for i in range(firstAdjustRoot):
# 在构造最大堆的时候，不会对最左侧的0进行处理，因为i不会取到firstAdjustRoot。
heapAdjust(numList, firstAdjustRoot - i, length)
print('第一次构建大顶堆完成...')
for i in range(length - 1):
numList[1], numList[length - i] = numList[length - i], numList[1]
# 由于大顶堆的堆顶元素是最大的，把它和数组最后的元素（堆的最下层最右元素）
# 进行互换，就相当于把最大值放在了最后，下一次，把最后一个元素撇出来，对剩下来的在排序
heapAdjust(numList, 1, length - i - 1)
# 由于交换之前，已经都调整为最大堆了，而交换之后，大部分都符合堆的规则，
# 只从堆顶元素（下标为1）开始，只进行局部的调整就好，
# 这时候不用再像刚开始构建最大堆一样从下往上，从右往左调整交换了。
return [numList[i] for i in range(1, len(numList))]
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = heap_sort3(dest)
print('最后的结果是:', dest[1:])
'''
[0, 5, 2, 7, 4, 8, 1, 6, 3]
[0, 5, 2, 7, 4, 8, 1, 6, 3]
[0, 5, 8, 7, 4, 2, 1, 6, 3]
[0, 8, 5, 7, 4, 2, 1, 6, 3]
第一次构建大顶堆完成...
[0, 7, 5, 3, 4, 2, 1, 6, 8]
[0, 6, 5, 3, 4, 2, 1, 7, 8]
[0, 5, 1, 3, 4, 2, 6, 7, 8]
[0, 3, 1, 2, 4, 5, 6, 7, 8]
[0, 4, 1, 2, 3, 5, 6, 7, 8]
[0, 2, 1, 4, 3, 5, 6, 7, 8]
[0, 1, 2, 4, 3, 5, 6, 7, 8]
最后的结果是: [0, 1, 2, 4, 3, 5, 6, 7, 8]
'''
C语言实现及优化
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b)
{
int temp = *b;
*b = *a;
*a = temp;
return;
}
void max_heapify(int arr[], int start, int end)
{
//建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子节点指标在范围内才做比较
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
return;
else //否则交换父子内容再继续子节点和孙节点比较
{
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
return;
}
void heap_sort(int arr[], int len)
{
int i;
//初始化，i从最後一个父节点开始调整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
for (i = len - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
return;
}
int main() {
int arr[] = {5, 2, 7, 4, 8, 1, 6, 3};
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
///////////////////////////////////////////////////////////
//优化的堆排序体现在不需要重新生成一个数组，而是直接原地进行所谓的堆排序。
void swap(int* a, int* b)
{
int temp = *b;
*b = *a;
*a = temp;
return;
}
void __shiftdown(int arr[],int n,int k)//下沉操作，传入数组以及需要排序的个数和下沉的索引
{
int e=arr[k];//记录首个下沉的节点的值
while(2*k+1<=n-1)//保证需要进行操作的节点至少有左孩子
{
int maxindex=2*k+1;//假设最大的子节点为左孩子
if(2*k+2<=n-1&&arr[2*k+2]>arr[maxindex])//如果存在右孩子并且右孩子比左孩子大
{
maxindex=2*k+2;//最大的子节点指向右孩子
}
if(e<arr[maxindex])//下沉节点的值要小于他的孩子节点
{
arr[k]=arr[maxindex];//下沉节点的值被大孩子的值替换
k=maxindex;//更新需要下沉节点的索引
}
else break;
}
arr[k]=e;//最后不能下沉的节点赋值为首下沉节点的值
}
void heap_sort2(int arr[],int n)//传入数组以及数组的大小
{
for(int i=(n-2)/2;i>=0;i--)//对数组进行heapfiy产生最大值arr[0]
__shiftdown(arr,n,i);//shiftdown所有可以下沉的父节点
for(int j=n-1;j>0;j--)
{
swap(&arr[0], &arr[j]);//把每次产生的最大值调到数组的后面去
__shiftdown(arr,j,0);
}
}
int main() {
int arr[] = {5, 2, 7, 4, 8, 1, 6, 3};
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort2(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
