堆排序的分析及实现

(二叉)堆是一个数组,它可以被看成一个近似的完全二叉树。二叉堆可以分为两种形式:最大堆和最小堆。若将记录按从大到小排列,建“小”顶堆。若将记录按从小到大排,建“大”顶堆。

说明:在堆排序算法中,我们使用的是最大堆,最小堆通常用于构造优先队列。

算法分析:时间复杂度是O(nlogn)。堆排序属于原址排序:任何时候都只需要常数个额外的元素空间存储临时数据。堆排序是不稳定的排序算法。

#include <stdio.h>
#define LEFT(i)        2 * i
#define RIGHT(i)    2 * i + 1

void MaxHeapAjust(int A[], int i, int len)            //调整节点i满足最大堆性质
{
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest, tmp;

if (l <= len && A[l - 1] > A[i - 1])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= len && A[r - 1] > A[largest - 1])
    {
        largest = r;
    }

if (i != largest)
    {
        tmp = A[i - 1];                       
        A[i - 1] = A[largest - 1];
        A[largest - 1] = tmp;

MaxHeapAjust(A, largest, len);
    }
}

void BuildMaxHeap(int A[], int len)                    //构造最大堆
{
    for (int i = len / 2; i > 0; i--)
    {
        MaxHeapAjust(A, i, len);
    }
}

void HeapSort(int A[], int len)                        //堆排序
{
    int tmp;
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; i--)
    {
        tmp = A[i - 1];
        A[i - 1] = A[0];
        A[0] = tmp;

MaxHeapAjust(A, 1, i - 1);
    }
}

int main(void)
{
    int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    HeapSort(A, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");

return 0;
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/5948845d7cc207ec55ba2498214a296b.html