代码之家  ›  专栏  ›  技术社区  ›  Chase

改进优先级队列堆中的密钥搜索时间复杂性

  •  2
  • Chase  · 技术社区  · 8 年前

    class Task{
    
        int ID;
        int Priority;
        int Time;
    
        public Task(int i, int p, int t){
            this.ID = i;
            this.Priority = p;
            this.Time = t;
        }
    
        //Getters, etc
    }
    

    它们按优先级存储在最大堆中,这很好。但是,如果我想找到具有特定ID值的任务对象,由于线性搜索(使用任务的基本数组作为堆),必须在O(n)时间内完成:

    public int getTimeOfID(int ID){            
    
        for(int i = 1; i < heapSize+1; i++){
            if (heap[i].getTaskID() == taskID){
                return heap[i].getTimeLeft();
            }
        }
    
        return -1;
    }
    

    我遇到了一些关于“修改堆”的引用,这些引用可以用来将ID搜索提高到O(1)倍,但还没有找到具体的实现示例。这有可能做到吗?如果有,我会怎么做?一个Java或pseudcode示例将不胜感激,但即使只是开始搜索的相关数据结构的名称也会很有帮助。谢谢你的帮助。

    //initial variables
    
    private Task[] heap;
    private int heapSize, capacity;
    int maxTasksHigh;
    
    //Constructor
    
    public PQ(int maxTasks){        
        this.capacity = maxTasks+1;
        heap = new Task[this.capacity];
        heapSize = 0;
        maxTasksHigh = maxTasks;
    }
    
    //Addition
    
    public void add(int ID, int time){        
        Task newTask = new Task(ID, time);
        heapSize++;
        heap[heapSize] = newTask;
        int target = heapSize;
    
        heap[target] = newTask;
        reorder(target);
    }
    
    //etc.
    
    1 回复  |  直到 8 年前
        1
  •  3
  •   Gilad Green Fábio    8 年前

    你可以做的是添加一个 HashMap ID Task

    然后,在添加或删除项目时,您可以从 HashMap<String, Task> 。这些操作将需要 O(1) 哈希图 除了最大堆之外,您还可以检查给定的 身份证件 .

    任务 不变的


    添加代码后更新:

    • 和 在构造函数中初始化它。
    • a.containsKey() 对于给定的 任务 。如果没有,则将其添加到最大堆和 .