我正在实现一种双端优先队列——min-max堆。您可以在这里查看有关min-max堆的更多信息。
插入和删除最小值操作的代码很简单,并且可以在网络上找到。但是,我也尝试在min-max堆上实现delete-max操作。
最初,我认为min-max堆中的delete-max与max-min堆中的delete-max相同(如果我们考虑包含最大元素的min-max堆子树,则类似于max-min堆)。因此,实现将简单且类似于min-max堆的delete-min。
但是,有一个问题:
如上图所示,尽管70是最大的元素,但最小-最大堆的最后一个元素(12)不在包含70的子树中。那么,在删除70后,我可以使用它来替换左子树留下的空缺吗?
如果我们不使用该元素,而是按照最大-最小堆的删除最大值过程,并使用20来替换空缺,则堆中插入的下一个元素将位于10的右子节点,并且永远没有9的右子节点。
所以,有人能帮帮我吗?
插入和删除最小值操作的代码很简单,并且可以在网络上找到。但是,我也尝试在min-max堆上实现delete-max操作。
最初,我认为min-max堆中的delete-max与max-min堆中的delete-max相同(如果我们考虑包含最大元素的min-max堆子树,则类似于max-min堆)。因此,实现将简单且类似于min-max堆的delete-min。
但是,有一个问题:
![enter image description here](https://istack.dev59.com/DC33H.webp)
如果我们不使用该元素,而是按照最大-最小堆的删除最大值过程,并使用20来替换空缺,则堆中插入的下一个元素将位于10的右子节点,并且永远没有9的右子节点。
所以,有人能帮帮我吗?