堆 C++ 代码

2016-08-01 11:38:31 暂无评论阳光倾城算法与数据结构 732

堆 C++ 代码

// File name: HeapTree.h
// Author: Arman Sahakyan
// Copyright (C) 2007, The CodeProject
// Contact: arman_sahakyan@edu.aua.am
#pragma once

class CHeapTree
{
    int m_nSize;
    int m_nMAX;
    const int m_nInitMax;
    struct _NODE {
        TID id;
        TDATA data;
    };
    _NODE *m_data;
public:
    CHeapTree(int nInitMax = 100);
    ~CHeapTree();
    bool IsEmpty() const { return m_nSize == 0; }
    int GetSize() const { return m_nSize; }
    void Insert(const TID &id, const TDATA &data);
    // Remove the element with the highest priority [if the heap is not empty]
    bool RemoveTop();
    bool RemoveAll();
    bool GetTopID(TID *pid) const {
        if (IsEmpty()) return false;
        *pid = m_data[0].id;
        return true;
    }
    bool GetTopData(TDATA *pdata) const {
        if (IsEmpty()) return false;
        *pdata = m_data[0].data;
        return true;
    }
    bool GetData(const TID &id, TDATA *pdata) const;
    // Change the data of a node with TID = id and reformat the heap
    bool ResetData(const TID &id, const TDATA &data);
private:
    // Reconstructs the heap be starting the element with index = iRoot
    void _ReformatHeap(int iRoot);
};

{
    m_nMAX = m_nInitMax;
    m_data = new _NODE[m_nMAX];
    m_nSize = 0;
}

{
    delete [] m_data;
}

{
    if (m_nSize == m_nMAX - 1)
    { // Resize the m_data array by doubling its size.
        m_nMAX += m_nMAX;
        _NODE *pTemp = m_data;
        m_data = new _NODE[m_nMAX];

            m_data[j] = pTemp[j];
        delete [] pTemp;
    }
    _NODE node = { id, data };
    m_data[m_nSize] = node;
    int iCur = m_nSize ++;
    int iParent = (iCur - 1) / 2;
    while (iParent >= 0 && m_data[iParent].data > m_data[iCur].data) {
        _NODE t = m_data[iCur];
        m_data[iCur] = m_data[iParent];
        m_data[iParent] = t;
        iCur = iParent;
        iParent = (iCur - 1) / 2;
    }
}

{
    if (IsEmpty()) return false;
    if (m_nSize == m_nMAX / 2)
    { // Resize the m_data array by shrinking its size twice.
        m_nMAX /= 2;
        _NODE *pTemp = m_data;
        m_data = new _NODE[m_nMAX];

            m_data[j] = pTemp[j];
        delete [] pTemp;
    }
    m_data[0] = m_data[-- m_nSize]; // move the last elem to the first place
    _ReformatHeap(0);
    return true;
}

{
    if (IsEmpty()) return false;
    delete [] m_data;
    m_nMAX = m_nInitMax;
    m_data = new _NODE[m_nMAX];
    m_nSize = 0;
    return true;
}

{

        if (m_data[j].id == id) {

                m_data[j].data = dataNew;
                _ReformatHeap(0);
            }
            else {
                m_data[j].data = dataNew;
                _NODE node = m_data[j];
                int iCur = j;
                int iParent = (iCur - 1) / 2;
                while (iParent >= 0 && m_data[iParent].data > m_data[iCur].data) {
                    _NODE t = m_data[iCur];
                    m_data[iCur] = m_data[iParent];
                    m_data[iParent] = t;
                    iCur = iParent;
                    iParent = (iCur - 1) / 2;
                }
            }
            return true;
        }
        return false; // id not found
}

{

        if (m_data[j].id == id) {
            *pdata = m_data[j].data;
            return true;
        }
    return false; // not found
}

{
    int iChild = 2 * iRoot + 1; // left child index

    {
        int iRightChild = iChild + 1; // right child index

        {
            if (m_data[iChild].data > m_data[iRightChild].data)
                iChild = iRightChild;
        }

            _NODE t = m_data[iRoot];
            m_data[iRoot] = m_data[iChild];
            m_data[iChild] = t;
            _ReformatHeap(iChild);
        }
    }
}