C++ 实现最大堆排序与最大优先队列

浏览数：32 / 时间：2015年06月08日

我一向赞同一个理念: 用代码实现简单逻辑是不需要注释的, 因此我也就不写注释了, 直接上代码:

#include <iostream>
#include <deque>
#include <limits>

inline int Parent (const int i)
{
    return std::move( i % 2
        ? (i - 1) / 2
        : (i - 2) / 2);
}

inline int Left (const int i)
{
    return std::move(2 * i + 1);
}

inline int Right (const int i)
{
    return std::move(2 * i + 2);
}

void MaxHeapify (std::deque<int> &ideq, int node)
{
    int largest = node;
    int limit = ideq.size ();

    auto SmallerThan = [&] (int child){ return (child < limit) && (ideq[largest] < ideq[child]); };

    int leftNode = Left (node);
    if (SmallerThan (leftNode)) {
        largest = leftNode;
    }

    int rightNode = Right (node);
    if (SmallerThan (rightNode)) {
        largest = rightNode;
    }

    if (largest != node) {
        std::swap (ideq[largest], ideq[node]);
        MaxHeapify (ideq, largest);
    }
}

std::deque<int>  BuildMaxHeap (std::deque<int> &ideq)
{
    std::deque<int> heap (ideq);
    for (int i = ideq.size () / 2 - 1; i > -1; --i) {
        MaxHeapify (heap, i);
    }
    return std::move (heap);
}

void HeapSort (std::deque<int> &ideq)
{
    auto heap = BuildMaxHeap (std::move(ideq));
    for (int i = ideq.size () - 1; i > -1; --i) {
        ideq[i] = std::move (heap[0]);
        heap.pop_front ();
        MaxHeapify (heap, 0);
    }
}

int HeapMaximum (std::deque<int> &heap)
{
    const int topValue = heap[0];
    return std::move(topValue);
}

int HeapExtractMax (std::deque<int> &heap)
{
    if (heap.empty()) {
        std::cerr << "heap overfow!\n";
    }
    int max = std::move(heap[0]);
    heap.pop_front ();
    MaxHeapify (heap, 0);
    return std::move (max);
}

void 
HeapIncreaseKey (std::deque<int> &heap, int &&node, int &&key)
{
    if (key < heap[node]) {
        std::cerr << "This key is smaller than current key!\n";
    }
    heap[node] = key;
    int parentNode = 0;
    while (( node > 0) && (parentNode = Parent(node), heap[parentNode] < key)){
        std::swap (heap[parentNode], heap[node]);
        node = parentNode;
    }
}

void MaxHeapInsert (std::deque<int> &heap, int key)
{

    heap.push_back (std::move(std::numeric_limits<int>::min()));
    HeapIncreaseKey (heap, heap.size() - 1, std::move(key));
}

void Print (const std::deque<int> &ideq)
{
    for (const auto &elem : ideq) {
        std::cout << elem << " ";
    }
}

int main ()
{
    std::ios::sync_with_stdio (false);
    std::deque<int> ideq{ 5, 13, 2, 25, 7, 17, 20, 9, 4};
    auto maxHeap = BuildMaxHeap (ideq);
    HeapIncreaseKey (maxHeap, 0, 30);
    HeapIncreaseKey (maxHeap, maxHeap.size() - 1, 40);
    MaxHeapInsert (maxHeap, 35);
    Print (maxHeap);
    std::cout << std::endl;
    return 0;
}