我正在实现一个min-max堆,一种双端优先级队列.您可以在这里查看
here以获取有关最小 – 最大堆的更多信息.
insert和delete-min操作的代码很简单,可以在网上找到.但是,我也试图在min-max堆上实现delete-max操作.
最初,我觉得min-max堆中的delete-max与max-min堆中的delete-max相同(如果我们考虑包含最大元素的min-max堆的子树,它类似于max-min堆).因此,实现将是简单的,类似于min-max堆的delete-min.
但有个问题：
从上图中可以看出,尽管70是最大元素,但最小 – 最大堆的最后一个元素(12)不在包含70的子树中.因此,我可以用它来替换左子树中留下的间隙删除70后？
如果我们不使用该元素而是遵循max-min堆的delete-max过程并使用20来替换间隙,则插入堆中的下一个元素将是10的右子,并且永远不会有正确的子元素9.
那么,任何人都可以帮助我吗？
