堆排序

综述

堆排序是指利用堆这种数据结构所设计的一种排序算法.
堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于（或者大于）它的父节点.

算法描述

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