About

• Binary Heap

• 数据结构

• 优先队列（priority queue）

Code

BinaryHeap

>
class BinaryHeap {
public:
    typedef size_t size_type;
BinaryHeap()
    : m_heap(0),m_size(0),m_capacity(0)
{
}

BinaryHeap(size_type max)
    : m_heap(0),m_capacity(max)
{
    m_capacity = max;
    m_size = 0;
    m_heap = new T[m_capacity + 1];
}

~BinaryHeap() { delete m_heap; }

BinaryHeap& operator = (const BinaryHeap& o)
{
    if (&o != this) {
        if (m_capacity != o.m_capacity) {
            delete m_heap;
            m_heap = new T[o.m_capacity + 1];
        }

        m_size = o.m_size;
        m_capacity = o.m_capacity;
        std::memcpy(m_heap,o->m_heap,(m_capacity + 1) * sizeof(T));
    }

    return *this;
}

template <size_type length>
BinaryHeap&amp; build(T (&amp;array)[length])
{
    if (m_capacity < length) {
        delete m_heap;
        m_capacity = length;
        m_heap = new T[m_capacity + 1];
    }

    m_size = length;
    std::memcpy(m_heap + tpos(),array,length * sizeof(T));

    for (size_type i = parent(m_size);i >= tpos();i --) {
        precolateDown(get(i),i);
    }
    return *this;
}

bool init(size_type max)
{
    if (m_capacity != 0 &amp;&amp; max < 3) {
        return false;
    }

    m_capacity = max;
    m_size = 0;
    m_heap = new T[m_capacity + 1];

    return true;
}

size_type size() const { return m_size; }

size_type capacity() const { return m_capacity; }

bool full() const { return m_size == m_capacity; }

bool empty() const { return m_size == 0U; }

void insert(const T&amp; e) { precolateUp(e,npos()); }

void deleteTop() { precolateDown(get(dpos()),tpos()); }

const T&amp; top() const { return ref(tpos()); }

void debugPrint() const
{
    if (!empty()) {
        print(m_heap + tpos(),m_heap + mpos() + 1);
    } else {
        std::cout <<"Empty!\n";
    }
}
private:

inline void precolateUp(const T& e,size_type pos)

{

for (; pos > 1 && compare(e,ref(parent(pos))); pos >>= 1) {

ref(pos) = ref(parent(pos));

}

*(m_heap + pos) = e;

}
inline void precolateDown(const T&amp; e,size_type pos)
{
    size_type child = 0;

    for (; lchild(pos) <= m_size; pos = child) {
        if ((child = lchild(pos)) != m_size &amp;&amp; compare(ref(child + 1),ref(child))) {
            child++;
        }           
        if (compare(e,ref(child))) {
            break;
        } else {
            ref(pos) = ref(child);
        }
    }

    ref(pos) = e;
}

//get element
inline T  get(size_type pos) const { return *(m_heap + pos); }

//ref element
inline T&amp; ref(size_type pos) const { return *(m_heap + pos); }

//top pos
inline size_type tpos() const { return 1; }

//max pos
inline size_type mpos() const { return m_size; }

//delete pos
inline size_type dpos() { return m_size --; }

//new pos
inline size_type npos() { return ++ m_size; }

//left child
inline size_type lchild(size_type cur) const { return cur << 1; }

//right child
inline size_type rchild(size_type cur) const { return (cur << 1) + 1; }

//parent
inline size_type parent(size_type cur) const { return cur >> 1; }

Cmp compare;
private:

T*          m_heap;

size_type   m_size;

size_type   m_capacity;

};

main

#include 
#include 
template 

void print(It beg,It end)

{

for (; beg < end; ++beg) {

std::cout << *beg << "\t";

}

std::cout << "\n";

}
int main()

{

using namespace std;
BinaryHeap<int,std::greater<int>> heap;

heap.init(10);
for (int i = 0; i < 10; i++) {
    heap.insert(i);
}
heap.debugPrint();

for (int i = 0;i < 10;i ++) {
    heap.deleteTop();
    heap.debugPrint();
}

int array[] = {1,3,4,6,7,8};

heap.build(array);
heap.debugPrint();

return 0;
}