2019-数据结构-数据结构6.0-优先级队列

Priority Queues(优先级队列)

1. 优先级队列

1. A priority queue is a collection of zero or more elements. Each element has a priority or value.一个优先级队列是0个或者更多元素的集合。每一个元素都有一个优先级或者值
2. 进入队列的时候有优先级，出队列优先出高优先级的.
   • 以下我们确定元素的优先级是通过数字的大小来确定。

1.1. 优先级队列分类(根据大小)

1. In a min priority queue the find operation finds the element with minimum priority, while the delete operation delete this element.在最小优先级队列中，当需要删除一个元素的时候，我们找到优先级最小的元素来删除
2. In a max priority queue, the find operation finds the element with maximum priority, while the delete operation delete this element.在最大优先级队列中，当需要删除一个元素的时候，我们找到优先级最大的元素来删除

2. 最大优先级队列(MaxPriorityQueue)

2.1. ADT(逻辑上最大优先级队列)

AbstractDataType  MaxPriorityQueue
{
instances
    finite collection of elements,each has a priority 有限的元素的结合，每个元素都有一个优先级
operations
    Create(): create an empty priority queue 创建一个空的优先级队列
    Size():  return number of element in the queue 返回队列中元素的个数
    Max(): return element with maximum priority 返回队列中拥有最高优先级的元素
    Insert(x): insert x into queue 插入x进入队列
    DeleteMax(x):delete the element with largest priority from the queue; return it in x;删除队列中最高优先级的元素，并且通过x返回它
}
实现
Use an unordered linear list 我们使用无序线性表来进行实现
Insertions are performed at the right end of the list, θ(1) 插入元素到链表的最右边(时间复杂度为常数)
A deletion requires a search for the element  with largest priority, θ(n)(需要查找到最高优先级的元素并且删除这个元素)

2.2. 物理实现:Heap

1. A max heap(min Heap):(最大堆)
   1. is A complete binary tree 最大堆是一个完全二叉树
   2. The value in each node is greater(less) than or equal to those in its children(if any).每一个节点上的值都大于(小于)或者等于他的子节点(如果有的话)

2. 注意:完全二叉树可以用矩阵来进行存储。
   • 从上向下一层一层进行记录。

2.3. 实现:最大优先级队列

template<class T>class MaxHeap
{
    public:
        MaxHeap(int MaxHeapSize=10);
        ~MaxHeap(){delete[]heap;}
        int size()const{return CurrentSize;}
        T Max(){
            if (CurrentSize==0) throw OutOfBounds();
            return heap[1];
        }
        MaxHeap<T>&insert(const T&x); 
        MaxHeap<T>& DeleteMax(T& x);
        void initialize(T a[], int size,  int ArraySize);
    private:
        int CurrentSize, MaxSize;
        T * heap;
}

1. 数组0号位置不用，也就是从Heap[1]开始使用

2.3.1. 最大堆的构造方法

template<class T> MaxHeap<T>::MaxHeap(int MaxHeapSize) {
    MaxSize=MaxHeapSize;
    Heap = new T[MaxSize+1];
    CurrentSize=0; 
}

2.3.2. 最大堆的插入算法

1. 在数组后面插入后，和其父结点进行比较，如果比父结点大，则交换，一直到不再大于其父结点。
   • 注意在最大优先级队列中的优先交换大的子树，不然会造成重复滤过。

2. 插入算法的时间复杂度:log₂(n)

template<class T>MaxHeap<T>& MaxHeap<T>:: Insert(const T& x){
    if(CurrentSize= =MaxSize) throw NoMem(); 
    int i=++CurrentSize;
    while(i!=1&&x>heap[i/2]){
        //0不使用
        heap[i]=heap[i/2];
        //不必每次都进行完全交换
        i/=2;
    }
    heap[i]=x;
    return *this;
}

2.3.3. 最大堆的删除算法

1. 将根删除，将数组最后一个(最后一层最后一个元素)换为根，然后进行比较。

template<class T>MaxHeap<T>&  MaxHeap<T>:: DeleteMax(T& x){
    if(CurrentSize==0) throw OutOfBounds(); 
    x = heap[1];
    //0无存储，这个就是root结点
    T y=heap[CurrentSize--];
    int i=1;//i标向树根
    ci=2;//ci先标到左子树
    while(ci<=CurrentSize){
        if(ci<CurrentSize && heap[ci]<heap[ci+1])//如果ci未越界，并且左子树的值小于右子树的值。
            ci++;//转向右子树
        if(y>=heap[ci]) break;
        heap[i]=heap[ci];
        i=ci;
        ci*=2;
    }
    heap[i]=y;//y是最后一个节点
    return *this;
}    

2. 插入算法的时间复杂度:log₂(n)

2.4. 初始化一个非空的最大优先级数列

1. 把初始指针指向最后一个节点的父结点(N/2)
2. 然后进行循环，然后每一个都换一遍就完成。
3. 总体来讲是从最后一个节点的父结点开始，对所有的非叶节点进行下滤操作。
   • 对于某一层节点进行下滤后，对其父结点继续进行下滤。

//C++
//注意是对每个子树进行递归处理
Template<class T> void MaxHeap<T>::Initialize (T a[],int size,int ArraySize) { 
    delete[] heap;
    heap=a;
    CurrentSize=Size;
    MaxSize=ArraySize;
    for( int i=CurrentSize/2; i>=1; i--) {
        T y=heap[i];
        int c=2*i;
        while(c <= CurrentSize){
            if(c<CurrentSize && heap[c]<heap[c+1])
                c++;
            if(y>=heap[c])
                break;
            heap[c/2] = heap[c];
            c*=2;
            //找到其子节点位置
        }
        heap[c/2]=y;
    }
}

// java 实现最大堆
private void buildHeap(){
    for( int i = currentSize / 2; i > 0 ; i-- )
        percolateDown(i);
}

4. 已经在内存中的算法复杂度分析(直接交换调整)
   • 对于不同层的节点，其下滤的计算量时不同的
   • 如何从感觉上立即这个问题:在数据的开始是不会到lgn的，而只有到后面的时候才能达到lgn(lgn = log₂n)

5. 不在内存(插入)中的算法复杂度分析(需要上滤)(需要进行其他操作调整)

3. 实现最小优先级队列

public class BinaryHeap {
    public BinaryHeap( )
    public BinaryHeap( int capacity )
    public void insert( Comparable x ) throws Overflow()
    public Comparable findMin( )
    public Comparable deleteMin( ) 
    
    public boolean isEmpty( )
    public boolean isFull( )
    public void makeEmpty( )
    
    private static final int DEFAULT_CAPACITY = 100
    private int currentSize
    private Comparable [ ] array;
    private void percolateDown( int hole ) 
    private void buildHeap( ) 
}
public BinaryHeap(){
    this( DEFAULT_CAPACITY );
}
public BinaryHeap( int capacity ) {  
    currentSize = 0;
    array = new Comparable[ capacity + 1 ];
}
public void makeEmpty( ) {
    currentSize = 0;
}
//最小堆的插入算法
public void insert( Comparable x ) throws Overflow() {
    if(isFull()) throw new Overflow(); 
    int hole = ++currentSize;
    for(;hole>1 && x.comparebleTo(array[hole/2])<0;hole/= 2){
        array[hole] = array[hole / 2];
    }
    array[ hole ] = x; 
}

1. 插入实例

public Comparable deleteMin(){
    if( isEmpty()) return null;
    Comparable minItem = findMin( );
    array[1] = array[currentSize--];
    percolateDown(1);
    return minItem;
}

//最小堆的，将最高顶部的元素向下传动，下滤算法
private void percolateDown(int hole) {  
    int child;
    Comparable tmp = array[hole];
    for(;hole*2<=currentSize;hole = child) {
        child = hole * 2;//切入到左子树
        if(child!=currentSize && array[child+1 ].compareTo(array[child])<0)
            child++;//如果没有到头，并且右子树比左子树小，则转向右边的子树
        if(array[child].compareTo(tmp)<0)
            array[hole] = array[child];//如果小则进行交换 
        else
            break;
    }
    array[hole] = tmp;
} 

2. 删除实例

3.1. 参考

1. 最详细的最小堆构建、插入、删除的过程图解

4. 优先级队列的应用

4.1. 堆排序(容易考)

1. initialize a max heap with the n elements to be sorted O(n) 初始化一个n个元素的最大堆，O(n)
2. each time we delete one element, then adjust the heap O(log₂n) 每次我们删除最大的元素，调整堆的时间复杂度为O(log₂n)
3. Time complexity is O(n)+O(nlog₂n)=O(nlog₂n)
4. 例子:{21,25,49,25*,16,08}

5. 堆排序是不稳定的:因为相同数据的位置不同
6. 堆排序每次删除最大的，然后把最大的放到最下方节点，把节点交换到顶部后进行下滤算法。

//c++
Template<class Type>void HeapSort(datalist<Type>&list){
    for(int i=(list.currentsize)/2;i>=1;i--) 
        FilterDown(i,list.currentsize);
    for(i=list.currentsize; i>1 ;i--){
        Swap(list.Vector[1],list.vector[i]); 
        FilterDown(1,i-1);
    }
}

public static void heapsort( Comparable [] a ) {
    for( int i = a.length / 2; i >= 1; i-- ) 
        percDown( a, i, a.length );
    for( int i = a.length ; i > 1; i-- ) { 
        swapReferences(a,1,i);
        percDown(a,1,i-1);
    }
}
private static void percDown( Comparable [] a, int i, int n ) {
    int child;
    Comparable tmp;
    for( tmp = a[ i ]; leftChild( i ) < n; i = child ) {
        child = leftChild( i );
        if( child != n – 1 && a[child ].compareTo( a[ child + 1 ]) < 0 )
            child++;
        if( tmp.compareTo( a[ child ] ) < 0 )
            a[ i ] = a[ child ]; 
        else  break;
    }
    a[ i ] = tmp;
}
private static int leftChild( int i ) {  
    return 2 * i + 1;
}     

4.2. The Selection Problem 查找问题

1. 问题描述：在N个元素中找出第K个最大元素。
2. 1A算法：读入N个元素放入数组， 并将其选择排序，返回适当的元素。算法时间复杂度：O( N²)
3. 1B算法:
   1. 将K个元素读入数组，并对其排序(按递减次序)。最小者在第K个位置上。
   2. 一个一个地处理其余元素：每读入一个元素与数组中第K个元素(在K个元素中为最小)比较，如果大于,则删除第K个元素，再将该元素放在合适的位置上(调整过程)。如果小于, 则舍弃。最后在数组K位置上的就是第K个最大元素。
   3. 运行时间(1B 算法)： O(K² + (N - K)K ) = O( NK ) 当 K = N / 2(向上取整), O( N² )
4. 例如：3, 5, 8, 9, 1, 10，找第3个最大元素。

4.2.1. 用堆来解决当前问题

1. 6A算法：假设求第K个最小元素
   1. 将N个元素建堆(最小)O( N )
   2. 执行K次delete，O( K*logN ) O( N + K * log N )
      1. 如果 K = (N/2)(向上取整)，O( N * log N )
      2. 如果 K = N ，O( N * log N ) 堆排序
   3. 如果是N取代最后一个是nlgn，可以考虑使用不同的情况来确定建立最大堆还是最小堆。
2. 6B算法：假设求第K个最大元素
   1. 读入前K个元素， 建立最小堆O( K )
   2. 其余元素一一读入：每读入一个元素与堆中第K个最大元素比(实际上是堆中最小元素)O(1)
      • 大于，则将小元素去掉(堆顶)，该元素进入，进行一次调整。O(log K )
      • 小于，则舍弃。
   3. O( K + ( N-K) * log K ) = O( N*log K)
   4. 当 K = (N/2)(向上取整) , θ(N * log N )
3. 对6A, 6B,用同样的数据进行测试， 只需几秒钟左右给出问题解。

5. 例题:2009统考题

1. 答案:A
2. 直接按照顺序一行一行生成。