2012-09-18 44 views
2

优先级队列中是否有MATLAB提供分的功能的PriorityQueue如何实现在MATLAB

import java.util.PriorityQueue; 
import java.util.*; 

public class MyQueue { 
    Comparator<Double> c; 
    PriorityQueue<Double> PQ; 

    public MyQueue() { 
    c = new Comparator<Double>(){ 
      public int compare(Double o1, Double o2){ 
       if(o2 > o1) { 
       return -1; 
       } else if(o1 > o2) { 
       return 1; 
       } else { 
       return 0; 
       } 
      } 
     }; 
    PQ = new PriorityQueue<Double>(1000,c); 
    } 

    public void addElement(double d) { 
    PQ.add(d); 
    } 

    public double removeElement() { 
    return(PQ.remove()); 
    } 
} 

我已经实现了在Java这个先决队列中的所有库。我可以从matlab中调用它。但是,我需要将每个成本与索引关联起来。我的意思是,这不仅是我需要存储的节点的成本,还有它的索引。我怎样才能做到这一点。我需要从MATLAB

+0

请在您的问题中提供更多详细信息。我不知道“min priorityqueue”是指什么。那是什么语言?它的功能是什么? – cjh

回答

4

由于发现here通过索引,你可以使用默认的Java PriorityQueue像这样:

>> q=java.util.PriorityQueue; 
>> q.add({value,index}); 

这是可用,因为Java 1.5中,这是所有Matlab的预先捆绑的释放,因为7.0.4。
否则,您可以使用file exchange中的那个,您必须编译它。

还有一个Simulink块,但我怀疑这是你的后。

+0

如何创建最小堆。所以它总是返回最小元素。 – user34790

+0

我可以看到我需要使用一个比较器,我需要用Java语言定义并在matlab中使用它。你能告诉我如何在matlab中使用我自己的java类 – user34790

+1

@ user34790有一点谷歌搜索出现了[本站点](http://www.mathworks.de/matlabcentral/answers/37185-cannot-call-java- class-from-matlab)和[this](http://www.cs.yale.edu/homes/spielman/ECC/javaMatlab.html)之一,[this](http://www.mathworks.com/matlabcentral/newsreader/view_thread/266022)一。这应该给你一个关于如何在Matlab中加载自定义类的好主意,并让你开始使用Comparator类。 –

3

下面是一个完全用matlab编写的优先级队列的调整大小的实现。您可以附加/耦合您想要的任何类型的数据/索引以及优先级值。此外,您可以在创建时通过传递给构造函数的布尔参数来切换/切换最小和最大优先级队列之间的行为。

classdef PriorityQueue < handle 

    properties (SetAccess = private)    
     numElements; 
     priorityList; 
     valueList; 
     flagMaxPriorityQueue; 
    end 

    methods (Access = public)  

     function obj = PriorityQueue(flagMaxPriorityQueue) 

      if ~exist('flagMaxPriorityQueue', 'var') 
       flagMaxPriorityQueue = true; 
      else 
       if ~(isscalar(flagMaxPriorityQueue) && islogical(flagMaxPriorityQueue)) 
        error('ERROR: invalid flagMaxPriorityQueue argument'); 
       end 
      end 

      obj.flagMaxPriorityQueue = flagMaxPriorityQueue; 
      obj.numElements = 0; 
      obj.priorityList = {}; 
      obj.valueList = {}; 

     end 

     function insert(obj, priority, value)  

      % increase the size of the array if full 
      if obj.numElements > 0 && obj.numElements + 1 > numel(obj.priorityList)         

       % double the size of the array and copy stuff 
       obj.priorityList = cat(1, obj.priorityList, cell(obj.numElements, 1)); 
       obj.valueList = cat(1, obj.valueList, cell(obj.numElements, 1)); 

      end 

      obj.numElements = obj.numElements + 1; 

      obj.priorityList{ obj.numElements } = priority; 
      obj.valueList{ obj.numElements } = value; 

      obj.swim(obj.numElements); 

     end 

     function [priority, value] = pop(obj) 

      if obj.isEmpty() 
       error('called pop() on an empty priority queue'); 
      end   

      priority = obj.priorityList{1}; 
      value = obj.valueList{1}; 

      obj.exch(1, obj.numElements);    
      obj.numElements = obj.numElements - 1;    
      obj.sink(1); 

      obj.priorityList{ obj.numElements + 1 } = []; 
      obj.valueList{ obj.numElements + 1 } = []; 

      % halve the size of the arrays if they get one-quarter full 
      if obj.numElements > 0 && obj.numElements == floor(numel(obj.priorityList)/4)     

       obj.priorityList(2 * obj.numElements + 1 : end) = []; 
       obj.valueList(2 * obj.numElements + 1 : end) = []; 

      end 

     end 

     function [flagEmpty] = isEmpty(obj)   

      flagEmpty = (obj.numElements == 0); 

     end 

     function [qSize] = size(obj) 

      qSize = obj.numElements; 

     end 

     function [priority, value] = peek(obj) 

      if obj.isEmpty() 
       error('requested max() of an empty priority queue'); 
      end   

      priority = obj.priorityList{1}; 
      value = obj.valueList{1}; 

     end 

    end  

    methods (Access = private) 

     function swim(obj, elPos) 

      while elPos > 1 && obj.compare(floor(elPos/2), elPos) 

       obj.exch(floor(elPos/2), elPos); 
       elPos = floor(elPos/2); 

      end 

     end 

     function sink(obj, elPos) 

      while 2 * elPos <= obj.numElements 

       j = 2 * elPos; 

       if j < obj.numElements && obj.compare(j, j+1) 
        j = j + 1; 
       end 

       if ~obj.compare(elPos, j) 
        break; 
       end 

       obj.exch(elPos, j); 
       elPos = j; 

      end 

     end 

     function [blnCmpResult] = compare(obj, e1, e2) 

      if obj.flagMaxPriorityQueue 
       blnCmpResult = (obj.priorityList{e1} < obj.priorityList{e2}); 
      else 
       blnCmpResult = (obj.priorityList{e1} > obj.priorityList{e2}); 
      end    

     end 

     function exch(obj, e1, e2) 

      temp = obj.priorityList{e1}; 
      obj.priorityList{e1} = obj.priorityList{e2}; 
      obj.priorityList{e2} = temp;    

      temp = obj.valueList{e1}; 
      obj.valueList{e1} = obj.valueList{e2}; 
      obj.valueList{e2} = temp;    

     end 

    end 

end % classdef