堆：排序算法与优先队列

堆

堆是一个数组，它可以被看成一个近似的完全二叉树，树上的每一个结点对应数组中的一个元素。每个子节点一定小于其父节点。使用MaxHeapify函数将当前结点移动到合适位置，BuildMaxHeap函数通过由下（数组长度的二分之一处（向下取整））向上（根节点）调用MaxHeapify函数实现最大堆，最小堆则相反。

inline int Parent(const int& x) { return x / 2;}
inline int Left(const int& x) { return x * 2;}
inline int Right(const int& x) { return x * 2 + 1;}
inline void Swap(int& a, int& b) { int t = a; a = b; b = t;}
inline void MaxHeapify(vector<int>& A, const int& i, const int& heapSize) {
    int l = Left(i);
    int r = Right(i);
    int largest = i;
    if(l < heapSize)
        if(A[l] > A[largest])
            largest = l;
    if(r < heapSize)
        if(A[r] > A[largest])
            largest = r;
    if(i != largest) {
        Swap(A[i], A[largest]);
        MaxHeapify(A, largest, heapSize);
    }
}
inline void BuildMaxHeap(vector<int>& A, const int& heapSize) {
    for(int i = heapSize / 2 - 1; i >= 0; i--)
        MaxHeapify(A, i, heapSize); 
}

堆排序

通过不断将最大堆的根节点（最大值）置于数组的最后位置，并对被交换到根节点的值进行MaxHeapify处理，将使数组变为有序的greater数组。HeapSort函数将调用上面的两个函数，并通过heapSize限制HeapSort函数的执行范围。

inline void HeapSort(vector<int>& A) {
    int heapSize = A.size();
    BuildMaxHeap(A, heapSize);
    for(int i = A.size() - 1; i >= 1; i--) {
        swap(A[0], A[i]);
        heapSize--;
        MaxHeapify(A, 0, heapSize);
    }
}

优先队列

priority_queue用于将一个集合中的元素按照特定顺序排列，c++中可以使用这一容器进行push，pop，top等操作。其中数据类型不可省略，容器类型选择数组类（vector， deque）（不知道使用vector和deque有什么区别，知道的同学请教请教啦o(￣▽￣)ブ），function与sort函数中的一样，可以自定义并且默认greater<>。

priority_queue<type, container, function> q;