0

我正在尝试解决一个有点困难的练习,因为我必须从树的模板类(RedBlack 或 BinarySearch 树的种类)开始实现优先级队列。

使用看起来像的模板

class Node
  int key
  Node left
  Node right
  Node parent
  int leftNodes
  int rightNodes

最初,当我必须插入一个新元素时,我尝试完全填充树的一个级别,然后使用 InOrderTreeTRaversal/Sort 算法填充一个数组并从该数组生成一个 BinarySearch 树,并用新的根元素替换原来的根元素。假设结果是一棵平衡的树。

不幸的是,这种方法似乎不合适,因为树必须模拟maxheap 属性,为每次插入/删除保持树的平衡(而且我的代码在完全填充树级别时效果不佳)。有可能实现具有堆功能的树吗?我的意思是一棵树,它的每个元素都大于或等于它的子元素,在插入后保持平衡,并且在删除根节点(更大的关键元素)时具有自动平衡功能?

4

1 回答 1

0

您可能想要实现二进制堆,请参阅http://en.wikipedia.org/wiki/Binary_heap

IIRC 这种数据结构的主要优点之一是它可以嵌入到数组中(因为平衡的性质)。Heapsort 使用这种数据结构进行就地排序。

于 2013-05-17T04:44:23.933 回答