Chinaunix首页 | 论坛 | 博客
  • 博客访问: 135355
  • 博文数量: 25
  • 博客积分: 588
  • 博客等级: 中士
  • 技术积分: 292
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-10 18:18
文章分类

全部博文(25)

文章存档

2012年(7)

2011年(18)

我的朋友

分类: C/C++

2011-06-02 16:30:42

为了理解思想,其简单实现如下:

#include
using namespace std;

//ÒÑintΪÀý ×î´ó¶Ñ
void make_heap(int a[], int size)
{
}
int heap_push(int a[], int n, int data)
{
    int i ;
    while ( n >= 1 ) {
        i = (n-1)/2;
        if (a[i] > data) break;
        a[n] = a[i];
        n = i;
    }
    a[n] = data;
    return n;
}

int heap_pop(int a[], int n)
{
    if (n==0) {
        return a[n];
    }
    int ret = a[0];
    int i = 0;
    int max = 2*i+1;
    while ( max <= n) {
        if ( max + 1 <= n ) {
            max = a[max] > a[max+1]?max:max+1;
        }
        if (a[max] <= a[n]) break;
        a[i] = a[max];
        i = max;
        max = 2*i+1;
    }
    a[i] = a[n];
    return ret;
}

void output(int a[], int n){
    for (int i=0; i        cout<    }
    cout<}
void heap_sort(int a[], int n)
{
    //build
    for (int i=0; i        heap_push(a, i, a[i]);
    }
    //sort
    for (int i=n-1; i>0; i--) {
        a[i] = heap_pop(a,i);
    }
}

int main(int argc, char **argv)
{
    int a[]={1, 100, 5, 2, 10, 11, 18, 90};

    int n = sizeof(a)/sizeof(int);
 
    heap_sort(a, n);

    for (int i=0; i        cout<    }   
    cout<
    return 0;
}
阅读(996) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~