0

I've been trying to implement a heap into my program. It seems to me that heaps are the same as binary trees. Is this the case with all heaps such as min heap and max heap since all that is being done is a traversal through the tree putting the largest/smallest node to the top?

Also, I've read that using 1-D arrays are only beneficial when we have a complete binary tree. If we don't have a complete binary tree, it would be more beneficial to use class that is a friend class to another? Why is that? Such as:

template<class T> class BT; // forward declartion -> added at edit

template<class T>
class BTNode{
    friend class BT<T>; // not sure why we need two classes
private:
    T data;
    BTNode<T> *leftChild; // what is the benefit of making a object Node?
    BTNode<T> *rightChild;
};

template<class T>
class BT{
private:
    BTNode<T> *root; // what is the benefit of having this root in another class?
};

Thank you in advance.

4

2 回答 2

1

标准库中有一个非常好的堆实现；你应该看看它（但它也是一个有用的学习练习来编写你自己的。）

二叉堆是一棵二叉树，但它可以有效地存储为向量。链接是隐式的。也就是说，位置i（从零开始）的节点的子节点在2i+1和2i+2。（堆中最多一个节点只有一个子节点。）这意味着您实际上不必存储链接，因此对于小数据对象（如整数），您至少可以节省三分之二的所需的空间。

维基百科有一篇关于二叉堆（通常存储在向量中的那种）的文章不错，但它也有许多关于其他类型堆的文章。

于 2012-11-17T03:19:02.823 回答
0

Include<algorithm>和 use std::make_heap，注意还有其他可以用堆做的功能。

于 2021-10-31T12:32:31.673 回答