| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 532 人关注过本帖, 1 人收藏
标题:《大话数据结构》读书笔记之二叉堆基本操作(最大堆)
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏(1)
 问题点数:0 回复次数:0 
《大话数据结构》读书笔记之二叉堆基本操作(最大堆)
/*
    Name: 二叉堆基本操作(最大堆)
    Copyright:
    Author: 巧若拙
    Date: 24-09-14 20:26
    Description:
    实现的最大堆的基本操作,包括向上,或向下调整二叉堆的第pos个元素,使其满足最大堆的特征;
    构造最大堆,利用最大堆进行堆排序和找第k大的数。
    如果要构造最小堆,则只需改变一下调整二叉堆时判断的条件即可。
*/

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

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

void MaxHeapSiftDown(ElemType a[], int n, int pos);//向下调整二叉堆的第pos个元素,使其满足最大堆的特征
void MaxHeapSiftUp(ElemType a[], int n, int pos);//向上调整二叉堆的第pos个元素,使其满足最大堆的特征
void CreateMaxHeap_1(ElemType a[], int n);//构造最大堆(较优)
void CreateMaxHeap_2(ElemType a[], int n);//构造最大堆(较差)
void HeapSort(ElemType a[], int n);//堆排序,得到非递减序列
int FindKthMin(ElemType a[], int n, int k);//寻找第k大的数(当k=1时,即找最小值)
int FindKthMax(ElemType a[], int n, int k);//寻找第k大的数(当k=1时,即找最大值)

int main(void)
{
    int i, k, n = MAXSIZE;
    ElemType a[MAXSIZE] = {2,4,7,5,1,6,8,9,3,3};
   
   puts("原数组:");
    for (i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
   
    CreateMaxHeap_2(a, n); //先构造一个最大堆
   
    puts("最大堆:");
    for (i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
   
    HeapSort(a, n);//堆排序,得到非递减序列
   
    puts("堆排序:");
    for (i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
   
    k = 4;
    printf("第%d大的数为%d\n", k, FindKthMin(a, n, k));//寻找第k大的数(当k=1时,即找最小值)
    k = 4;
    printf("第%d大的数为%d\n", k, FindKthMax(a, n, k));//寻找第k大的数(当k=1时,即找最大值)
   
    return 0;
}

/*
函数功能:向下调整二叉堆的第pos个元素,使其满足最大堆的特征
初始条件:二叉堆a[]已经存在
操作结果:定位第pos个元素的孩子结点中较大的一个,当孩子结点比双亲结点大时,通过向上移动孩子结点值的方式,确保双亲结点大于孩子结点,以满足最大堆的特征。
采用类似插入排序的方法,向上移动数据,腾出插入位置,将原堆中第pos个元素向下调整到适当的位置。
注意:因C语言的数组下标从0开始,故第pos个元素在数组中表示为a[pos-1]。
若要删除二叉堆的第一个元素,则将最后一个元素放到根部,然后对根结点做向下调整操作,得到新的最大堆。
*/   
void MaxHeapSiftDown(ElemType a[], int n, int pos)
{
    ElemType temp = a[pos-1];
    int child = pos * 2; //指向左孩子
   
    while (child <= n)
    {
        if (child < n && a[child-1] < a[child]) //有右孩子,且右孩子更大些,定位其右孩子
            child += 1;
        
        if (a[child-1] > temp) //通过向上移动孩子结点值的方式,确保双亲大于孩子
        {
            a[pos-1] = a[child-1];
            pos = child;
            child = pos * 2;
        }
        else
            break;
    }
   
    a[pos-1] = temp; //将temp向下调整到适当位置
}

/*
函数功能:向上调整二叉堆的第pos个元素,使其满足最大堆的特征
初始条件:二叉堆a[]已经存在
操作结果:定位第pos个元素的双亲结点,当孩子结点比双亲结点大时,通过向下移动双亲结点值的方式,确保双亲结点大于孩子结点,以满足最大堆的特征。
采用类似插入排序的方法,向下移动数据,腾出插入位置,将原堆中第pos个元素向上调整到适当的位置。
注意:因C语言的数组下标从0开始,故第pos个元素在数组中表示为a[pos-1]。
若要插入新元素,则将新元素插入到堆的最末位置,然后对新元素做向上调整操作,得到新的最大堆。
*/   
void MaxHeapSiftUp(ElemType a[], int n, int pos)
{
    ElemType temp = a[pos-1];
    int parents = pos / 2; //指向双亲结点
   
    if (pos > n) //不满足条件的元素下标
        return;
   
    while (parents > 0)
    {
        if (a[parents-1] < temp) //通过向下移动双亲结点值的方式,确保双亲大于孩子
        {
            a[pos-1] = a[parents-1];
            pos = parents;
            parents = pos / 2;      
        }
        else
            break;
    }
    a[pos-1] = temp; //将temp向上调整到适当位置
}

/*
函数功能:构造最大堆(较好)
初始条件:数组a[]已经存在
操作结果:通过逆序向下调整非叶子结点,将一个普通数组改造成最大堆。
*/   
void CreateMaxHeap_1(ElemType a[], int n)
{
    int i;
   
    for (i=n/2; i>0; i--)
    {
        MaxHeapSiftDown(a, n, i);
    }
}

/*
函数功能:构造最大堆(较差)
初始条件:数组a[]已经存在
操作结果:通过不断插入新元素,对新元素做向上调整操作,得到新的最大堆。  
*/   
void CreateMaxHeap_2(ElemType a[], int n)
{
    int i;
   
    for (i=1; i<=n; i++)
    {
        MaxHeapSiftUp(a, n, i);
    }
}


/*
函数功能:堆排序,得到非递减序列
初始条件:数组a[]已经存在
操作结果:先构造一个最大堆,然后依次把根元素交换到适当的位置,重新调整得到新的最大堆。
逐次减小堆的长度,直到长度为1。
*/   
void HeapSort(ElemType a[], int n)
{
    int i;
    ElemType temp;
   
    CreateMaxHeap_1(a, n); //先构造一个最大堆
   
    for (i=n-1; i>0; i--) //删除二叉堆的第一个元素,将其与第i个元素交换,然后向下调整得到新的最大堆。
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;

        MaxHeapSiftDown(a, i, 1); //对根结点做向下调整操作,得到长度为i的新最大堆
    }
}

/*
函数功能:寻找第k大的数(当k=1时,即找最小值)
初始条件:数组a[]已经存在
操作结果:先构造一个最大堆,然后遍历数组元素[k..n-1],若元素不小于a[0],不做任何操作;
否则替换a[0],确保a[0]是第k大的数,再对根结点做向下调整操作,维持最大堆的特性
*/   
int FindKthMin(ElemType a[], int n, int k)
{
    int i;
   
    CreateMaxHeap_2(a, k); //先构造一个长度为k的最大堆
   
    for (i=k; i<n; i++)
    {
        if (a[i] < a[0]) //确保a[0]是第k大的数
        {
            a[0] = a[i];
            MaxHeapSiftDown(a, k, 1); //对根结点做向下调整操作
        }
    }

    return a[0];
}

/*
函数功能:寻找第k大的数(当k=1时,即找最大值)
初始条件:数组a[]已经存在
操作结果:利用堆排序的方法,先构造一个最大堆,然后依次把根元素交换到适当的位置,重新调整得到新的最大堆。
做k趟排序,就可以找到第k大的数。
*/   
int FindKthMax(ElemType a[], int n, int k)
{
    int i;
    ElemType temp;
   
    CreateMaxHeap_1(a, n); //先构造一个长度为n的最大堆
   
    for (i=n-1; i>n-k; i--) //做k趟排序,找到第k大的数
    {
        temp = a[0]; //将第一个元素和第i个元素交换
        a[0] = a[i];
        a[i] = temp;
        
        MaxHeapSiftDown(a, i, 1); //对根结点做向下调整操作,得到长度为i的新最大堆
    }
   
    return a[0];
}
搜索更多相关主题的帖子: 元素 include 读书笔记 Copyright 
2014-09-25 20:39
快速回复:《大话数据结构》读书笔记之二叉堆基本操作(最大堆)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020187 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved