algorithm ch6 priority queque

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

int  HeapMaximum(int a[], int &heapSize)
{
    return a[1];
}
int HeapExtractMax(int a[], int &iHeapSize)
{
    if(iHeapSize < 1)
    {
        cout << "heap underflow." << endl;
    }
    int iMax = a[1];
    a[1] = a[iHeapSize];
    iHeapSize = iHeapSize - 1;
    MaxHeapify(a, 1, 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 > 1 && a[parent(iPos)] < a[iPos])
    {
        swap(a[iPos], a[parent(iPos)]);
        iPos = parent(iPos);
    }
}
void MaxHeapInsert(int a[], int iKey, int &iHeapSize)
{
    iHeapSize += 1;
    a[iHeapSize] = -INT_MAX;
    HeapIncreaseKey(a, iHeapSize, iKey);
}

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

好好学习,总会有收获。

时间: 03-28

algorithm ch6 priority queque的相关文章

algorithm ch6 heapsort

堆排序利用的是堆这种数据结构来对进行排序,(二叉)堆数据结构是一种数组对象,它可以被视为一棵完全的二叉树,树的每个节点与数组中存放该节点的值得那个元素对应.这里使用最大堆进行排序算法设计,最大堆就是parent(i) > leftchild(i) 且parent(i) > rightchild(i),首先利用迭代法进行建堆. void MaxHeapify(int *a, int node, int iHeapSize) { int iIndexL = left(node); int iInd

Heapsort 和 priority queue

一.二叉堆含义及属性: 堆(heap)亦被称为:优先队列(priority queue),是计算机科学中一类特殊的数据结构的统称.堆通常是一个可以被看做一棵完全二叉树的数组对象.在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权.堆即为解决此类问题设计的一种数据结构.同垃圾收集存储的堆含义不同. 表示堆的数组A有两个属性: A.length : 代表A数组的元素个数; A.heapsiz

Algorithm Part I:Priority Queues

1.binary heap实现 BinaryHeap.h #ifndef BINARYHEAP_H #define BINARYHEAP_H class BinaryHeap { public: BinaryHeap(int N); bool isEmpty(); void exchange(int i,int j); void insert(int key); int delMax(); int getMax(); virtual ~BinaryHeap(); protected: priva

Linux: the schedule algorithm in Linux kernel

Linux kernel里面用到的一个叫 CFS (Completely-Fair-Scheduler)的调度算法.在网上找的描述都很不直观,很难读.但是找到了一篇很通俗易懂的(大道至简啊...): http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt 为了防止链接失效,粘贴全文如下: This is the CFS scheduler. 80% of CFS's design can be summed up in

初学图论-Dijkstra单源最短路径算法基于优先级队列(Priority Queue)的实现

这一次,笔者使用了STL库中的优先级队列(Priority Queue)来完成Dijkstra算法中extract-min()语句(即从未选中的节点中选取一个距离原点s最小的点)的功能.由于优先级队列的插入.删除操作只需要logn的时间花费,因此降低了不少运行时间. 本文使用C++实现了这一基本算法.参考<算法导论>第24.3节. /**  * Dijkstra's Single Source Shortest Path Algorithm in C++  * Time Cost : O(Ml

优先队列(堆) Priority Queue

Priority Queue Definition & Description: In computer science/data structures, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated wi

Non-blocking algorithm(非阻塞算法,非阻塞同步的算法实现)

Non-blocking algorithm In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blockingalgorithm is lock-free if there is guarant

Algorithm | Sort

Bubble sort Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wron

Heap &amp;amp; Priority Queue

Heap & Priority Queue Definition & Description: In computer science/data structures, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" as