# 基本数据结构介绍及其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;

}