《算法设计手册》中的附加条款3-7说：
假设您有权访问一个平衡的字典数据结构，该结构支持在O（logn）时间内执行搜索、插入、删除、最小值、最大值、后续值和前置值的每个操作。解释如何修改插入和删除操作，使它们仍然需要O（logn），但现在最小和最大需要O（1）时间。（提示：考虑使用抽象字典操作，而不是摆弄指针之类的东西。）
如果没有这些暗示，我认为这个问题相当容易。
这是我的解决方案：
对于树，我只保持一个指针min总是指向最小值，另一个指针max总是指向最大值。
插入x时，我只是将min.key与x.key，if min.key > x.key, then min = x;进行比较，如果需要，也可以对max进行比较。
删除x时，if min==x, then min = successor(x); if max==x, then max = predecessor(x);
但是这个暗示说我不能搞指针之类的东西。我的解决方案中有指针吗？
如果我们不能使用额外的点，我怎么能得到最小值和最大值的O（1）？
感谢
你的答案和我给出的答案是一样的——你没有弄乱指针，你只是在存储最小值/最大值。
所以，只要更加自信：）
您可以使用最小最大堆来实现更新/删除的log（N）时间和获得最小/最大值的恒定时间
我认为你不能同时得到最大值和最小值的O（1）。
无论如何，这本书希望你自己发现二进制堆。如果你想自己做，就不要看链接。只需考虑以下提示："树的根始终包含最小值"（如果您希望"最大值"为O（1），则为最大值）。
我将使用两个二进制堆：一个最小堆和一个最大堆。在每一个中，你都存储了一半的元素，这样你就可以在O（1）时间内访问max和min。最小堆包含具有最小元素的一半，最大堆包含具有较大元素的一半。插入/删除操作仍将为O（logn）。插入新元素时，只需检查它应该放在哪个堆中。
存储两个值，最大值和最小值。每次删除时都需要对这些内容进行检查并可能进行更新。如果正在删除最小值，请调用后续项，更新最小值并删除旧项。插入时，将新项目与最小值/最大值进行比较，如果它替换了其中任何一个，则相应地更新最小值/最高值