代码之家  ›  专栏  ›  技术社区  ›  soham joshi

java如何知道当在PriorityQueue中时,一个items键被更改,以重新堆化更改的节点[duplicate]

  •  -2
  • soham joshi  · 技术社区  · 8 年前
        class PQItem implements Comparable<PQItem>{
    public int key;
    
    public PQItem(int key) {
        this.key = key;
    
    }
    
    @Override
    public int compareTo(PQItem o) {
        return this.key - o.key;
    }
    
    public String toString(){
        return this.key+"";
    }
    

    }

        PriorityQueue<PQItem> pq = new PriorityQueue<>();
        PQItem pq1 = new PQItem(45);
        PQItem pq2 = new PQItem(1);
        PQItem pq3 = new PQItem(4);
        PQItem pq4 = new PQItem(3);
    
        pq.offer(pq1);
        pq.offer(pq2);
        pq.offer(pq3);
        pq.offer(pq4);
    
        pq1.key = 40;
        pq2.key = -4;
    
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    

    以上按预期顺序打印 3. 4. 40

    问题是我想知道更改密钥的操作是否在O(lg n)中完成,在更改的节点上使用Heapify。如果这样做了,java如何检测我在其中一个对象上设置属性以触发该节点上的heapify过程。

    1 回复  |  直到 8 年前
        1
  •  0
  •   user207421    8 年前

    它没有,而且在Javadoc中特别这么说。