堆排序算法详解与代码实现

// Hello.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int Num = 7;
int data[Num]={12,2,16,1,35 ,20 ,48};  //数据

void max_heapify(int data[],int i,int size) //以某个节点为根节点的子树进行调整，调整为大根堆      假设传进去的 i = 0【实际是从底向上进行，i=0只是说明效果】
{
    int left = 2*i + 1;     //注意左右子节点标号与自然标号的差异    left = 1
    int right = 2*i + 2;  //right = 2
    int largest_num = i;         //定义最大节点号为传进来的 i 节点号。     

    if( left < size   &&   data[left]>data[i] ) //如果左子结点存在，且对应数据大于原根节点内的数据    假设条件成立，则 largest_num = 1;
    {
        largest_num = left;              //将最大值的节点标定为左子结点
    }
    if( right< size   &&   data[right]>data[largest_num] )     //如果右子结点存在，且对应数据大于已确定的最大节点号对应的值   假设又成立，则 largest_num = 2;
    {
        largest_num = right;           //将最大值的节点标定为右子结点
    }
    if( largest_num != i )    //如果最大值对应的节点号发生改变，则需要将最大值节点号对应值与原节点号对应值互换   与上面假设对应，则交换 data[0] 与 data[2] 中的值
    {
        int temp = data[largest_num];
        data[largest_num] = data[i];
        data[i] = temp;
        max_heapify(data,largest_num, size);   //递归调用 ，直到所有都被遍历   第二遍为(data,2,size)
    }