2

我正在研究二进制堆的自定义实现。我需要一个最小堆和一个最大堆，这样我就可以创建一个“销售 - 购买”出价系统。

我的问题是，当有新的报价（销售或购买）出现然后有购买时，“人员”应该从堆中弹出并跟踪他们的列表。我想知道如何跟踪二进制堆中的键（名称）。

例如，在外部类中，我有类似的东西。

public class OuterClass{
    public static HashMap<String, Integer> buyers = new HashMap<>();
    public static HashMap<String, Integer> sellers = new HashMap<>();

    public static BHeap<String, Integer> buyHeap = new BHeap<>(); 
    public static BHeap<String, Integer> sellHeap = new BHeap<>();
    //etc...
}

在我的二进制堆实现中，我有这样的东西。

public class BHeap <K extends Comparable<? super K>, V extends Comparable<? super V>> {
    protected ArrayList<K> keys = new ArrayList<>();
    protected ArrayList<V> values = new ArrayList<>();
    //do heap stuff
}

当我比较两个堆时，我会继续弹出直到找到匹配项（即买入价>=卖出价）。但是，当我可以返回的唯一信息是 VAL 时，我如何跟踪谁（KEY）出售和购买了

4

1 回答 1

0

我的解决方案是在执行时，pop()或者peek()(returns top element)该函数应该返回 KEY 而不是 VALUE（但在 pop() 中你删除两者）。然后在外部类上，您跟踪 HashMap 上发生的事情（这可能是多余的，但对于另一件事来说很好）

另一种解决方案是将 ArrayList 占位符设为“Person”或“Node”类型。我实际上选择了一个基于树的解决方案

class Node<K, V extends Comparable<? super V>>{
    Node<K, V> lchild = null, rchild = null, parent = null;
    V value;
    K key;
}

但它被特别要求是一个数组实现

于 2014-11-26T03:26:22.287 回答