基本数据结构介绍及其C++实现（上）

// BinaryHeapTree.hpp

_Pragma("once")




#include 




class BinaryHeapTree

{

    public:

        BinaryHeapTree(int32_t capacity = 100);

        BinaryHeapTree(int32_t capacity, int32_t* array, int32_t n);

        BinaryHeapTree(const BinaryHeapTree& bht);

        BinaryHeapTree(BinaryHeapTree&& bht);

        BinaryHeapTree& operator = (const BinaryHeapTree& bht);

        ~BinaryHeapTree();




        bool empty() const;

        int32_t getRootValue() const;

        int32_t getLastLeafValue() const;

        bool insert(int32_t value);

        bool deleteRootValue();

        bool deleteValue(int32_t curIndex);

        void display() const;




    private:

        bool isRoot(int32_t curIndex) const;

        int32_t getLevelNum(int32_t curIndex) const;// 获取当前节点的层号，根节点的层号是0

        int32_t getParentIndex(int32_t curIndex) const;

        int32_t getLeftChildIndex(int32_t curIndex) const;

        int32_t getRightChildIndex(int32_t curIndex) const;




    private:

        void bubbleUp(int32_t curIndex);

        void bubbleDown(int32_t curIndex);




    private:

        void init(const BinaryHeapTree& bht);




    private:

        int32_t capacity;

        int32_t eleNum;

        int32_t * entries;// 下标0不用，从下标1开始

};




// BinaryHeapTree.cpp




#include "BinaryHeapTree.hpp"

#include 

#include




BinaryHeapTree::BinaryHeapTree(int32_t capacity)

{

    std::cout << "BinaryHeapTree::BinaryHeapTree(int capacity)" << std::endl;

    this->capacity = capacity;

    eleNum = 0;

    entries = new int32_t[capacity + 1];// 下标0不用，浪费一个元素,方便计算

}




// O(n), n为节点个数。

BinaryHeapTree::BinaryHeapTree(int32_t capacity, int32_t* array, int32_t n)

{

    if(capacity < n)

    {

        throw std::logic_error("BinaryHeapTree capacity < n");

    }

    this->capacity = capacity;

    this->eleNum = n;

    this->entries = new int32_t[capacity + 1];// 下标0不用，浪费一个元素,方便计算

    memcpy(entries + 1, array, n * sizeof(int32_t));

    for(int32_t i = n / 2; i > 0; --i)

    {

        bubbleDown(i);

    }

}




void BinaryHeapTree::init(const BinaryHeapTree& bht)

{

    capacity = bht.capacity;

    eleNum = bht.eleNum;

    entries = new int32_t[capacity + 1];// 下标0不用，浪费一个元素,方便计算

    memcpy(entries, bht.entries, (capacity + 1) * sizeof(int32_t));

}




BinaryHeapTree::BinaryHeapTree(const BinaryHeapTree& bht)

{

    std::cout << "BinaryHeapTree::BinaryHeapTree(const BinaryHeapTree& bht)" << std::endl;

    init(bht);

}




BinaryHeapTree::BinaryHeapTree(BinaryHeapTree&& bht)

{

    std::cout << "BinaryHeapTree::BinaryHeapTree(BinaryHeapTree&& bht)" << std::endl;

    capacity = bht.capacity;

    eleNum = bht.eleNum;

    entries = bht.entries;

    bht.entries = nullptr;

}




BinaryHeapTree& BinaryHeapTree::operator = (const BinaryHeapTree& bht)

{

    std::cout << "BinaryHeapTree& BinaryHeapTree::operator = (const BinaryHeapTree& bht)" << std::endl;

    if(this == &bht)

    {

        return *this;

    }

    if(entries != nullptr)

    {

        delete []entries;

    }

    init(bht);

    return *this;

}




BinaryHeapTree::~BinaryHeapTree()

{

    if(entries != nullptr)

    {

        delete []entries;

    }

}




bool BinaryHeapTree::empty() const

{

    return (0 == eleNum);

}




int32_t BinaryHeapTree::getRootValue() const

{

    if(empty())

    {

        throw std::logic_error("BinaryHeapTree empty");

    }

    return entries[1];

}




int32_t BinaryHeapTree::getLastLeafValue() const

{

    if(empty())

    {

        throw std::logic_error("BinaryHeapTree empty");

    }

    return entries[eleNum];

}




bool BinaryHeapTree::insert(int32_t value)

{

    if(eleNum >= capacity)

    {

        throw std::logic_error("BinaryHeapTree full");

    }

    ++eleNum;

    entries[eleNum] = value;

    bubbleUp(eleNum);

    return true;

}




bool BinaryHeapTree::deleteRootValue()

{

    if(empty())

    {

        throw std::logic_error("BinaryHeapTree empty");

    }

    entries[1] = entries[eleNum];

    --eleNum;

    bubbleDown(1);

    return true;

}




bool BinaryHeapTree::deleteValue(int32_t curIndex)

{

    if(empty())

    {

        throw std::logic_error("BinaryHeapTree empty");

    }

    if(curIndex > eleNum)

    {

        throw std::logic_error("BinaryHeapTree curIndex invalid");

    }

    entries[curIndex] = entries[eleNum];

    --eleNum;

    bubbleUp(curIndex);

    bubbleDown(curIndex);

    return true;

}




bool BinaryHeapTree::isRoot(int32_t curIndex) const

{

    return (1 == curIndex);

}




int32_t BinaryHeapTree::getLevelNum(int32_t curIndex) const

{

    return std::log(curIndex) / std::log(2);

}




int32_t BinaryHeapTree::getParentIndex(int32_t curIndex) const

{

    return (curIndex / 2);

}




int32_t BinaryHeapTree::getLeftChildIndex(int32_t curIndex) const

{

    return (2 * curIndex);

}




int32_t BinaryHeapTree::getRightChildIndex(int32_t curIndex) const

{

    return (2 * curIndex + 1);

}




// 任何节点都只能有一个父节点（根节点除外），所以bubbleUp相对简单一些

void BinaryHeapTree::bubbleUp(int32_t curIndex)

{

    if(isRoot(curIndex))

    {

        return;

    }

    int32_t parentIndex = getParentIndex(curIndex);

    if(entries[curIndex] > entries[parentIndex])

    {

        std::swap(entries[curIndex], entries[parentIndex]);

        bubbleUp(parentIndex);

    }

}




// 节点可能没有子节点、只有左子节点、有左右两个子节点，不同的情况处理不同，bubbleDown比bubbleUp复杂一些。

void BinaryHeapTree::bubbleDown(int32_t curIndex)

{

    int32_t leftChildIndex = getLeftChildIndex(curIndex);

    int32_t rightChiledIndex = getRightChildIndex(curIndex);

    if(leftChildIndex > eleNum)

    {

        // 没有子节点,无需比较和交换

        return;

    }

    else if(eleNum < rightChiledIndex)

    {

        // 只有左子节点,没有右子节点，根据完全二叉树（二叉堆树）的定义，这个左子节点是不会有任何子节点的。

        if(entries[curIndex] < entries[leftChildIndex])

        {

            std::swap(entries[curIndex], entries[leftChildIndex]);

        }

    }

    else

    {

        // 有左、右两个子节点, 左右子节点是可能含有子节点的，所以需要继续比较和交互.

        if(entries[leftChildIndex] < entries[rightChiledIndex])

        {

            if(entries[curIndex] < entries[rightChiledIndex])

            {

                std::swap(entries[curIndex], entries[rightChiledIndex]);

                bubbleDown(rightChiledIndex);

            }

        }

        else

        {

            if(entries[curIndex] < entries[leftChildIndex])

            {

                std::swap(entries[curIndex], entries[leftChildIndex]);

                bubbleDown(leftChildIndex);

            }

        }

    }

}




void BinaryHeapTree::display() const

{

    for(int32_t i = 1 ; i <= eleNum; ++i)

    {

        std::cout << entries[i] << ",";

    }

    std::cout << std::endl;

}