Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

BinaryHeap

以向量存储，下标从0开始

// 构建堆
void BuildHeap(vector<int> & BinaryHeap)
{
    int size = (int)BinaryHeap.size();
    int i,j,k,l;

    for(i = size / 2 - 1;i >= 0;--i)
    {
        j = i;
        
        while(true)
        {
            k = 2 * j;
            l = k + 2;
            k = k + 1;

            if(l < size)
            {
                if(BinaryHeap[j] > min(BinaryHeap[k],BinaryHeap[l]))
                {
                    if(BinaryHeap[l] > BinaryHeap[k])
                    {
                        swap(BinaryHeap[j],BinaryHeap[k]);
                        j = k;
                    }
                    else
                    {
                        swap(BinaryHeap[j],BinaryHeap[l]);
                        j = l;
                    }
                }
                else
                    break;
            }
            else if(k < size)
            {
                if(BinaryHeap[j] > BinaryHeap[k])
                {
                    swap(BinaryHeap[j],BinaryHeap[k]);
                    j = k;
                }
                else
                    break;
            }
            else
                break;
        }
    }
}
// 插入
void insert(vector<int> & BinaryHeap,int x)
{
    int size = (int)BinaryHeap.size();
    int i = size + 1;
    BinaryHeap.resize(i);

    int j = i / 2 - 1;
    while(j >= 0 && BinaryHeap[j] > x)
    {
        BinaryHeap[i - 1] = BinaryHeap[j];
        i = j + 1;
        j = (j + 1) / 2 - 1;
    }
    BinaryHeap[i - 1] = x;
}
// 删除最小元
int DeleteMin(vector<int> & BinaryHeap)
{
    int size = (int)BinaryHeap.size();
    int min = BinaryHeap[0],last = BinaryHeap[size - 1];

    int i,child;
    for(i = 0;i * 2 + 2 < size;i = child)
    {
        // find smaller child
        child = i * 2 + 1;
        if(child < size && BinaryHeap[child + 1] < BinaryHeap[child])
            ++child;
        
        // percolate one level
        if(BinaryHeap[child] < last)
            BinaryHeap[i] = BinaryHeap[child];
        else
            break;
    }
    BinaryHeap[i] = last;
    BinaryHeap.resize(size - 1);

    return min;
}

 


posted on 2007-04-09 16:05 Dain 阅读(505) 评论(0)  编辑 收藏 引用 所属分类: 程序


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理