#include <iostream>
#include <vector>
namespace algorithm
{
namespace sort
{
namespace heap_sort
{
//用于执行堆排序的类
//由于使用顺序存储结构来表示一棵树
//所以使用裸指针而不是STL中的元素
template<typename E>
class Tree
{
private:
const size_t size__;
E *const elements;
public:
Tree(const size_t &size, E *elements) :
size__(size),elements(
reinterpret_cast<E *>(
malloc((size + 1)*sizeof(E))
)
)
{
if (elements == NULL) memset(this->elements, 0, sizeof(int));
else memcpy((this->elements + 1), elements, size * sizeof(E));
}
E *getElements() const
{
return this->elements;
}
const size_t size() const
{
return this->size__;
}
//从完全二叉树中序号为root的结点开始在序号为[1,range]范围内进行筛选
inline void adjust(const size_t &root, const size_t &range) const
{
//这个筛选过程怎么那么费脑筋呢
bool hasLeftChild = 2 * root < range;
bool hasRightChild = (2 * root + 1) < range;
if (hasLeftChild&&hasRightChild)
{
//妈的，这样写逻辑真是太他妈的蛋疼
if (this->getElements()[root] <= this->getElements()[2 * root] &&
this->getElements()[root] <= this->getElements()[2 * root + 1])
{
//不需要调整，返回
return;
}
else
{
//从两个叶子结点中找一个最小的替换到头
if (this->getElements()[2 * root] < this->getElements()[2 * root + 1])
{
E temp = this->getElements()[root];
this->getElements()[root] = this->getElements()[2 * root];
this->getElements()[2 * root] = temp;
//然后要对以这个为根的进行筛选
adjust(2 * root, range);
}
else
{
E temp = this->getElements()[root];
this->getElements()[root] = this->getElements()[2 * root + 1];
this->getElements()[2 * root + 1] = temp;
//然后要对以这个为根的进行筛选
adjust(2 * root + 1, range);
}
}
}
if ((!hasLeftChild) && (!hasRightChild))
{
//叶子节点，一样不需要调整
}
if (hasLeftChild == true && hasRightChild == false)
{
if (this->getElements()[root] < this->getElements()[2 * root])
{
return;
}
else
{
//交换，然后筛选左子树
E temp = this->getElements()[root];
this->getElements()[root] = this->getElements()[2 * root];
this->getElements()[2 * root] = temp;
//然后要对以这个为根的进行筛选
adjust(2 * root, range);
}
}
//其实不会有只有右子树没有左子树的情况的，但是还是要写上
if (hasLeftChild == false && hasRightChild == true)
{
if (this->getElements()[root] < this->getElements()[2 * root + 1])
{
return;
}
else
{
//交换，然后筛选左子树
E temp = this->getElements()[root];
this->getElements()[root] = this->getElements()[2 * root + 1];
this->getElements()[2 * root + 1] = temp;
//然后要对以这个为根的进行筛选
adjust(2 * root + 1, range);
}
}
}
//这个重载的无参构造函数用于在建堆时进行全局筛选
inline void adjust() const
{
//进行首次筛选
for (size_t i = this->size() / 2; i > 0; --i)
{
this->adjust(i, this->size());
}
}
//应该考虑如何进行筛选
inline void sort() const
{
//用于排序并存储在原来的位置
adjust();
for (size_t remaining = size(); remaining > 1; remaining--)
{
adjust(1, remaining);
//替换到最后一个
E temp = this->elements[1];
this->elements[1] = this->elements[remaining];
this->elements[remaining] = temp;
}
}
};
}
}
}
int main(int argc, char ** argv)
{
using algorithm::sort::heap_sort::Tree;
//为了统一下标，应该浪费第一位
int data[10] = { 2,0,1,5,3,0,1,8,6,6 };
Tree<int> tree = Tree<int>(10,data);
for (size_t i = 1; i <= 10; i++)
{
std::cout << *(tree.getElements() + i) << " ";
}
std::cout << std::endl << std::flush;
tree.sort();
for (size_t i = 1; i <= 10; i++)
{
std::cout << *(tree.getElements() + i) << " ";
}
std::cout << std::endl << std::flush;
tree.adjust();
for (size_t i = 1; i <= 10; i++)
{
std::cout << *(tree.getElements() + i) << " ";
}
std::cout << std::endl << std::flush;
tree.sort();
for (size_t i = 1; i <= 10; i++)
{
std::cout << *(tree.getElements() + i) << " ";
}
std::cout << std::endl << std::flush;
}
网友评论