如何设计混合哈希表和堆的数据结构

Question

我的问题如下：

给定一个三元组列表，它们存储在一个名为 hash_heap 的数据结构中（我不确定这个名称，只是意味着它应该是哈希表和堆的混合）。我希望数据结构提供以下方法，

index_by_first_col(key) // the method could help find the a triple stored in it by matching the first column. It expects the searching is running at constant time
get_min_by_third_col() // the method get the minimum triple sort according to the third column, it is also expects the method is running at constant time.
insert_new_elt(triple) // add new trip, running at constant time

是否可以实现这样的数据结构？我知道哈希表可以支持第一种方法，堆可以支持第二种和第三种方法，但我不知道如何将它们混合在一起。有什么想法吗？

谢谢！

Answer 1

有一个非常简单的数据结构可以满足您声明的要求。

使用哈希表（在第一列上键入）并另外存储指向最小元素的指针（在第三列上）。然后，index_by_first_col 是哈希表查找，get_min_by_third_col 是指针取消引用，insert_new_elt 是哈希表插入和比较以确定 min 指针是否需要更新。

请注意，这给出了 O(n) 删除（最小值），但您没有说明删除的任何要求。