学步园

原文链接：http://www.nowamagic.net/algorithm/algorithm_HeapSortStudy.php

在程序设计相关领域，堆(Heap)的概念主要涉及到两个方面：

• 一种数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。
• 垃圾收集存储区，是软件系统可以编程的内存区域。

本文所说的堆，指的是前者。

堆排序的时间复杂度是O(nlgN)，与快速排序达到相同的时间复杂度。但是在实际应用中，我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现，往往比堆排序具有更好的表现。堆排序的主要用途，是在形成和处理优先级队列方面。另外，如果计算要求是类优先级队列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同样是很适合的数据结构。

基础知识

堆一般用数组表示，比如数组A数组的长度Length(A)，堆在数组中的元素个数HeapSize(A)。一般说来，HeapSize(A) <= Length(A)，因为数组A当中可能有一些元素不在堆中。

假设节点I是数组A中下标为i的节点。

• Parent(i) : return Floor(i/2); //I的父节点下标，Floor(i)表示比i小的最大整数。
• Left(i) : return 2*i; //I的左子节点
• Right(i) : return 2*i+1; //I的右子节点

含有n个元素的堆A的高度是: Floor(lgn)。

#include <stdio.h>
#include <stdlib.h>

void HeapSort(int num[],int size);
void BuildHeap(int num[] ,int size);
void PercolateDown(int num[] , int index,int size);
void PrintHeap(const char* strMsg,int array[],int nLength);
void Swap(int num[] , int v, int u);

int main(int argc, char *argv[])
{
    int data[13]= {8,5,4,6,13,7,1,9,12,11,3,10,2};
    HeapSort(data,13);

    system("PAUSE");
    return 0;
}


void HeapSort(int num[] ,int size)
{
    int i;
    int iLength=size;

    PrintHeap("Befor Sort:",num,iLength);

    BuildHeap(num,size);// 建立小顶堆

    for (i = iLength - 1; i >= 1; i--)
    {
        Swap(num, 0, i);// 交换
        size--;// 每交换一次让规模减少一次
        PercolateDown(num, 0,size);// 将新的首元素下滤操作
        PrintHeap("Sort Heap:",num,iLength);
    }
}

// 建堆方法，只需线性时间建好
void BuildHeap(int num[] ,int size)
{
    int i;
    for (i = size / 2 - 1; i >= 0; i--)  // 对前一半的节点（解释为“从最后一个非叶子节点开始，将每个父节点都调整为最小堆”更合理一些）
    {
        PercolateDown(num, i,size);// 进行下滤操作
        PrintHeap("Build heap:",num,size);
    }
}

// 对该数进行下滤操作，直到该数比左右节点都小就停止下滤
void PercolateDown(int num[] , int index,int size)
{
    int min;// 设置最小指向下标
    while (index * 2 + 1<size)  // 如果该数有左节点，则假设左节点最小
    {
        min = index * 2 + 1;// 获取左节点的下标
        if (index * 2 + 2<size)  // 如果该数还有右节点
        {
            if (num[min] > num[index * 2 + 2])  // 就和左节点分出最小者
            {
                min = index * 2 + 2;// 此时右节点更小，则更新min的指向下标
            }
        }
        // 此时进行该数和最小者进行比较，
        if (num[index] < num[min])  // 如果index最小，
        {
            break;// 停止下滤操作
        }
        else
        {
            Swap(num, index, min);// 交换两个数，让大数往下沉
            index = min;// 更新index的指向
        }
    }// while
}

// 给定数组交换两个数的位置
void Swap(int num[] , int v, int u)
{
    int temp = num[v];
    num[v] = num[u];
    num[u] = temp;
}

void PrintHeap(const char* strMsg,int array[],int nLength)
{
    int i;
    printf("%s",strMsg);
    for(i=0; i<nLength; i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
}