堆定义、建堆算法、堆插入删除算法、堆排序

堆定义、建堆算法、堆的插入删除算法、堆排序算法

1、堆（heap）定义

堆其实就是二叉堆的简称，那何为二叉堆呢？

二叉堆其实是完全二叉树或者是近似二叉树。二叉堆必须满足两个特性：

• 父节点的键值必须大于等于或小于等于任何一个子节点的键值。
• 每个结点的左子树和右子树必须都是一个二叉堆（都是最大堆或最小堆）。

当父节点的键值总是大于等于任何一个子结点的键值时为最大堆。当父节点的键值总是小于等于任何一个子结点的键值时为最小堆。

2、建堆算法及排序算法

堆的存储：一般都用数组来表示堆，按从上到下，从左到右对节点进行编号，规律：i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

# include  
  
void main()
{  
    void Sort(int[]);
	int a[10] ={26,5,77,1,61,11,59,15,48,19};  
    Sort(a);  
}  
//堆排序算法 
void Sort(int a[] ) 
{  
    void Display(int [],char []);
    void Adjust(int [],int , int ) ;
    int n = 10;//取得数组总长度，及堆最大的序号  
    int temp = 0;  
    Display(a, "Before sort : ");  //输出函数，下面有定义 
	for(int i=n/2; i>0; i--) 
	{  
        Adjust(a, i - 1, n);//从倒数第二层的最后一个根节点开始调整堆  
        Display(a, "建立最大堆 : ");  
    }  
    printf("---------------------------------------n");  
    for (int i = n - 2; i >= 0; i--) 
	{//这是堆排序的具体算法，思想是每次取出堆的最顶层根节点，即数组下标为0，然后与最后一个节点即i+1交换，
	 //这样对于最大堆而言，随着最后一个结点的前移，最大值总是被留在后面。。循环过后就是倒序了。。  
        temp = a[i + 1];//取出最后一个元素  
        a[i + 1] = a[0];//取出第一个元素，即顶层根节点  
        a[0] = temp;//交换位置  
  
        Adjust(a, 0, i + 1);//调整堆  
        Display(a, "重建立最大堆 : ");  
    }  
  
    Display(a, "After  sort : ");  
}  
    /** 
     * 调整最大堆的算法
     * @param a　要调整的数组，即堆 
     * @param i　调整的根节点，即起始位置 
     * @param n　要调整的终止位置 
     */  
void Adjust(int a[],int i, int n) 
{  
    int j = 0;  
    int temp = 0;  
  
    temp = a[i]; //取出根节点  
    j = 2 * i + 1;  //左孩子节点  
  
    while (j <= n - 1) 
	{  
        if (j < n - 1 && a[j] < a[j + 1])//比较左右孩子，取出较大的孩子  
            j++;  
  
        if (temp >= a[j]) //如果根节点大于孩子节点则退出循环，不用调整  
        	break;  
  
        a[(j - 1) / 2] = a[j];//较大的孩子节点值赋值给根节点  
  
        j = 2 * j + 1;//继续寻找左孩子  
    }  
  
    a[(j - 1) / 2] = temp;//将根节点赋值给最后一个空出来的节点  
}  
    //打印堆内容  
void Display(int a[], char b[]) 
{  
    printf("%sn",b);  
  
    for (int i = 0; i < 10; i++)  
        printf("%d ",a[i]);  
  
    printf("n");  
     
  
}  
</code></pre>

3、插入删除算法

* 堆的插入

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中，代码如下：


//  新加入i结点  其父结点为(i - 1) / 2  
void MinHeapInsert(int a[], int i)  
{  
    int j, temp;  
      
    temp = a[i];  
    j = (i - 1) / 2;      //父结点  
    while (j >= 0 && i != 0)  
    {  
        if (a[j] <= temp)  
            break;  
          
        a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点  
        i = j;  
        j = (i - 1) / 2;  
    }  
    a[i] = temp;  
}  

* 堆的删除
按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。代码如下：

//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
void MinHeapDelete(int a[], int i, int n)  
{  
    int j, temp;  
  
    temp = a[i];  
    j = 2 * i + 1;  
    while (j < n)  
    {  
        if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的  
            j++;  
  
        if (a[j] >= temp)  
            break;  
  
        a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点  
        i = j;  
        j = 2 * i + 1;  
    }  
    a[i] = temp;  
}  
//在最小堆中删除数  
void MinHeapDeleteNumber(int a[], int n)  
{  
    Swap(a[0], a[n - 1]);  
    MinHeapFixdown(a, 0, n - 1);  
}  








			
赞微海报分享