MHeap.h

Go to the documentation of this file.

#ifndef MHEAP_H
#define MEAH_H

#include "MercuryVector.h"

template<typename T>
class MHeap
{
public:
    MHeap();
    void push(const T&);
    void pop();
    T& head();
    bool empty() const { return m_heap.size() == 1; }
private:
    void swap(unsigned int a, unsigned int b);
    void percolateUp(unsigned int x);
    void percolateDown(unsigned int x);
    unsigned int floor(unsigned int a, unsigned int b);
    MVector< T > m_heap;
};

template<typename T>
MHeap< T >::MHeap()
{
    m_heap.push_back(T()); //blank element first
}

template<typename T>
void MHeap< T >::swap(unsigned int a, unsigned int b)
{
    T tmp(m_heap[a]);
    m_heap[a] = m_heap[b];
    m_heap[b] = tmp;
}

template<typename T>
unsigned int MHeap< T >::floor(unsigned int a, unsigned int b)
{
    unsigned int r = a%b;
    return a/(b-r);
}

template<typename T>
void MHeap< T >::push(const T& t)
{
    unsigned int size = m_heap.size();
    if (size == 1)
        m_heap.push_back(t);
    else if (size > 1)
    {
        m_heap.push_back(t);
        percolateUp(size);
    }
}

template<typename T>
void MHeap< T >::percolateUp(unsigned int x)
{

    unsigned int parent = floor(x-1, 2);
    if (m_heap[parent] > m_heap[x])
    {
        swap(parent, x);
        percolateUp(parent);
        x = parent;
    }
}

template<typename T>
void MHeap< T >::percolateDown(unsigned int x)
{
    unsigned int child = x*2;
    if (child < m_heap.size())
        if (m_heap[x] > m_heap[child])
        {
            swap(child, x);
            percolateDown(child);
        }
    if (child+1 < m_heap.size())
        if (m_heap[x] > m_heap[child+1])
        {
            swap(child+1, x);
            percolateDown(child+1);
        }
}

template<typename T>
T& MHeap< T >::head()
{
    return m_heap[1];
}


template<typename T>
void MHeap< T >::pop()
{
    if (m_heap.size() > 1)
    {
        m_heap[1] = m_heap[m_heap.size()-1];
        m_heap.remove(m_heap.size()-1);
        percolateDown(1);
    }
}

#endif

/* 
 * Copyright (c) 2007 Joshua Allen
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *  -   Redistributions of source code must retain the above
 *      copyright notice, this list of conditions and the following disclaimer.
 *  -   Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the distribution.
 *  -   Neither the name of the Mercury Engine nor the names of its
 *      contributors may be used to endorse or promote products derived from
 *      this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

---

Hosted by