堆

在介绍堆前需要引入一个二叉树的概念

完全二叉树：若二叉树有k层，除第k层外，1-(k-1)层均达到最大值，则称为完全二叉树。

满二叉树：节点数n与层数k满足n=2^k-1关系的二叉树。

满二叉树一定是完全二叉树。

堆：满足父节点总是大于等于两个子节点或父节点总是小于等于两个子节点的完全二叉树，则称为堆。即节点值y1,y2,y3,yi…yn始终满足关系

堆排序

简介

堆排序是一种利用堆这种数据结构而设计的一种排序算法。堆排序最早是由图灵奖的得主罗伯特·弗洛伊德和斯坦福大学计算机科学系教授威廉姆斯提出的。

步骤

1. 初始化堆：主要完成把数组或链表结构的数据转化为大顶堆或小顶堆的任务
2. 排序：将堆顶（即最大值或最小值）与最后一个节点交换，然后将这个最值从堆中剔除（即堆节点减一），最后从第一个节点开始重新处理二叉树，使之满足堆的定义。
3. 重复执行排序步骤，直到完成排序。

代码实现

/*堆排序*/

#include <iostream>
using namespace std;

void swap( int *a, int *b )
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

int *heap_sort( int *arr, int p, int len )
{
    int dad = p;
    int son = 2 * dad + 1;

    while ( son <= len )
    {
        if ( son + 1 <= len && arr[son] < arr[son + 1] ) 
        { 
            son++; 
        } 
        if ( arr[dad] > arr[son] )
        {
            return 0;
        }
        else
        {
            swap( &arr[dad], &arr[son] );
            dad = son;
            son = dad * 2 + 1;
        }
    }

    return arr;
}



int main()
{
    int arr[] = { 12, 54, 74, 44, 61, 3, 91, 52, 447, 31 };
    int len = sizeof( arr ) / sizeof( arr[0] );
    int i = len / 2 - 1;

    //初始化堆
    while ( i >= 0 )
    {
        heap_sort( arr, i--, len-1 );
    }

    i = len-1;
    //排序
    while ( i )
    {
        swap( &arr[0], &arr[i--] );
        heap_sort( arr, 0, i );
    }
    i = 0;
    while ( len > i )
    {
        cout << arr[i] << endl;i++;
    }

    return 0;
}

执行结果：