algorithm ch6 priority queque

堆数据结构的一个重要用处就是：最为高效的优先级队列。优先级队列分为最大优先级队列和最小优先级队列，其中最大优先级队列的一个应用实在一台分时计算机上进行作业的调度。当用堆来实现优先级队列时，需要在队中的每个元素里存储对应的应用对象句柄(handle)。这里对象柄用数组下标表示，因为在堆操作中，堆元素会改变在数组中的位置，所以具体实现中为了重新定义堆元素，我们需要更新应用对象中的数组下标。简单的实现代码如下：

int  HeapMaximum(int a[], int &heapSize)

{

    return a[];

}

int HeapExtractMax(int a[], int &iHeapSize)

{

    if(iHeapSize < )

    {

        cout << "heap underflow." << endl;

    }

    int iMax = a[];

    a[] = a[iHeapSize];

    iHeapSize = iHeapSize - ;

    MaxHeapify(a, , iHeapSize);

    return iMax;

}

void HeapIncreaseKey(int a[], int iPos, int iKey)

{

    if(iKey < a[iPos])

    {

        cout << "new key is smaller than current key." << endl;

        return;

    }

    a[iPos] = iKey;

    while(iPos >  && a[parent(iPos)] < a[iPos])

    {

        swap(a[iPos], a[parent(iPos)]);

        iPos = parent(iPos);

    }

}

void MaxHeapInsert(int a[], int iKey, int &iHeapSize)

{

    iHeapSize += ;

    a[iHeapSize] = -INT_MAX;

    HeapIncreaseKey(a, iHeapSize, iKey);

}

同时还找到一份不错的学习代码http://www.cnblogs.com/Anker/archive/2013/01/23/2873951.html

好好学习，总会有收获。

巴特西

algorithm ch6 priority queque

最新文章

热门文章