堆排序实现

前段时间在看侯捷的STL源码剖析，看到堆这一章顺带复习了一下堆排序，我们所说的堆一般指的是二叉堆，下面先来看下二叉堆的定义。

二叉堆定义

二叉堆是完全二叉树或是近似完全二叉树。

二叉堆满足两个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

 

最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

存储

二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置节点的子节点位置在2n+1、2n+2。这种方式便于查找节点的子节点及父节点。如，位置0的子节点在1、2，位置1的子节点在3、4。

二叉堆插入

 

插入操作一般把数据插入到数组的最后面，然后，由此节点向上调整二叉堆，以满足二叉堆的性质。代码如下：

 

void push_heap(int array[], int hopeInd, int topInd, int value){
    int parent = (hopeInd - 1) / 2;
    while (hopeInd > topInd && array[parent] < value){
        array[hopeInd] = array[parent];
        hopeInd = parent;
        parent = (hopeInd - 1) / 2;
    }
    array[hopeInd] = value;
}

 

 

二叉堆删除

二叉堆的删除操作与插入相反，插入是“向上冒”，而删除时“向下沉”，即把根节点移除并把最后一个节点移到最前面，然后由此节点往下调整二叉堆。代码如下：

 

void fix_down_heap(int array[], int hopeInd, int size, int value){
    int secondChild = hopeInd * 2 + 2;
    int topInd = hopeInd;
    while (secondChild < size){
        if (array[secondChild-1] > array[secondChild]){
            secondChild--;
        }

        array[hopeInd] = array[secondChild];
        hopeInd = secondChild;
        secondChild = hopeInd * 2 + 2;
    }

    if (secondChild == size){
        array[hopeInd] = array[secondChild-1];
        hopeInd = secondChild - 1;
    }

    push_heap(array, hopeInd, topInd, value);
}

 

数组堆化

在进行二叉树排序之前，需要把数组转化为二叉堆，即数组堆化。由最后一个非子节点开始至根节点，一个个向下进行堆调整，即可完成堆的建立。建立堆的代码如下：

 

void make_heap(int array[], int size){
    int hopeInd = (size - 2) / 2;
    while (hopeInd >= 0){
        fix_down_heap(array, hopeInd, size, array[hopeInd]);
        hopeInd--;
    }
}

 

排序实现

对数组建立堆之后就可以进行排序操作了。根据二叉堆的性质，根节点是所有节点中值最大或最小的，因此堆排序就是一个不断删除根节点然后调整堆直到只有一个元素的过程。代码如下：

 

void swap(int& a, int& b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

 

void heapSort(int array[], int length){
    make_heap(array, length);

    for (int i=length-1; i>0; i--){
        swap(array[i], array[0]);
        fix_down_heap(array, 0, i, array[0]);
    }
}

至此，堆排序结束。

 

 

刚开始学习写博客，如有不足之处，欢迎指出。谢谢！