最小堆和最小堆排序

1、原理介绍：百度百科

2、最小堆的构造和添加

#include <stdio.h>
#define N 9 // 最小堆得元素个数

int minHeap[N]; // 存放最小堆的数组
int index1 = ; // 最小堆数组索引

void add(int d) // 向最小堆内添加数据
{
    if(index1 >= N)
    {
        printf("Out of range!\n");
        return;
    }
    int t = index1; // t指向存放位置
    int pt = (t - ) / ; // 父节点
    while(t > ) // t指向0位置时结束循环
    {
        if(minHeap[pt] > d) // 当父节点数据比插入数据大时，将父节点数据下移
        {
            minHeap[t] = minHeap[pt];
            t = pt;
            pt = (t - ) / ;
        }
        else // 找到合适位置
            break;
    }
    minHeap[t] = d; // 最后存放数据位置
    index1++;
}
int main()
{
    int t[] = {, , , , , , , , };
    int i;
    for(i=; i<; i++)
    {
        add(t[i]);
    }

    for(i=; i<; i++) // 输出测试
    {
        printf("%d ", minHeap[i]);
    }
    printf("\n");
    return ;
}
           

3、最小堆排序算法

在构造最小堆时，没有必要一个节点一个节点的添加，可以将原来的数组看成一颗完全二叉树。并且知道数组元素个数。那么从最后一个非叶子节点的节点开始逐步向前，直到第一个节点。对每个节点与它的最小孩子节点比较，如果大于最小孩子节点，那么将孩子节点上移，该节点下移。直到找到不大于孩子节点的位置或者到孩子节点。将该节点值保存。

排序思想：

a. 使用变量index1=n-1。

b. 数组长度为n，循环n-1次。

c. 每次循环，构造(调整)一次最小堆，此时注意调整的数组长度为index1+1。排好序的元素不再调整。

d. 交换第一个元素和第index1个元素，index1–。(较小元素放到后面)

e. 直到循环结束，输出排序结果。

void outputt(int t[], int len) // 数组输出
{
    int i;
    for(i=; i<len-; i++) // 输出测试
    {
        printf("%d ", t[i]);
    }
    printf("%d\n", t[i]);
}

void heap(int t[], int len) // 调整二叉树生成堆
{
    int i;
    int l, r;
    int min, u;
    int ti, values;
    for(i=len/-; i>=; i--) // 数组下标从0开始
    {
        ti = i; // 指向i元素存放位置
        values = t[i];
        while(ti < len)
        {
            l =  * ti + ;
            r = l + ;
            u = -;

            if(l < len) // 取孩子中最小者最小
            {
                min = t[l];
                u = l;
            }
            if(r < len && t[r] < min)
            {
                min = t[r];
                u = r;
            }

            if(u == -) // 到达叶子节点
                break;

            if(values > min)
            {
                t[ti] = min;
                ti = u;
            }
            else // 不大于孩子节点
                break;
        }
        t[ti] = values; // 存放该值
    }
}

void heapSort(int t[], int len) // 进行堆排序
{
    int tmp;
    int index1 = len - ;
    while(index1 > ) // 当未排序的只剩一个时，没必要再排
    {
        heap(t, index1 + ); // 构造或调整最小堆
        tmp = t[];
        t[] = t[index1];
        t[index1] = tmp;
        outputt(t, ); // 查看排序过程
        index1--;
    }
}
           

4、最小堆删除元素。每次删除第一个元素，并且把最后一个元素拿过来补充第一个元素，然后对这个新的二叉树进行调整使其满足最小堆的条件，不过此时调整仅从根节点调整即可。其实第三部分的堆排序中，只有第一次需要从最后一个非叶子节点进行调整，其他情况从根节点调整即可。最大堆的使用在最小堆的某些判断条件处更改即可。