MATLAB-STL/PriorityQueue.m at master · Emut/MATLAB-STL · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
classdef PriorityQueue < handle
    %PriorityQueue custom order random insert queue with mixed elements
    %   Umut Ekici 2019
    %   https://github.com/Emut/MATLAB-STL
    %   numutekici@gmail.com
    %
    %   Front of the queue is always the smallest element*
    %   Push and Pop with O(log(n)), Top with O(1)
    %   *smallest is the default behaviour, this can be changed by giving
    %   any function handle taking 2 elements and returning a logical
    %   value as a result of this comparison (e.g. @ge would make this a
    %   max heap

    %properties(Access = private)
    properties
        memberCount;
        keyHeap;
        compareKeys;
    end

    methods
        function obj = PriorityQueue(compareHandle)
            obj.memberCount = 0;
            if nargin < 1
                obj.compareKeys = @le;
            else
                obj.compareKeys = compareHandle;
            end
        end
        function push(obj, key)
            obj.memberCount = obj.memberCount + 1;
            pivotInd = obj.memberCount;
            obj.keyHeap{pivotInd} = key;

            while(true)
                parentInd = obj.getParentOf(pivotInd);
                if(parentInd < 0)
                    break;  %reached the root
                end
                if(~obj.compareKeys(obj.keyHeap{pivotInd}, obj.keyHeap{parentInd}))
                    break;  %parent is smaller than inserted, heap OK
                end
                %else swap the 2 keys
                obj.swapKeys(pivotInd, parentInd);
                pivotInd = parentInd;   %continue upwards
            end
        end

        function retKey = pop(obj)
            retKey = obj.keyHeap{1};    %return the top
            obj.swapKeys(1, obj.memberCount);   %bring end key to top
            obj.memberCount = obj.memberCount - 1;

            pivotInd = 1;
            while(true)
                leftInd = obj.getLeftChildOf(pivotInd);
                if(leftInd < 0)
                    break;  %reached bottom
                end
                rightInd = obj.getRightChildOf(pivotInd);

                if(obj.compareKeys(obj.keyHeap{pivotInd}, obj.keyHeap{leftInd}))
                    leftOK = true;
                else
                    leftOK = false;
                end

                if(rightInd < 0)
                    rightOK = true;
                elseif(obj.compareKeys(obj.keyHeap{pivotInd}, obj.keyHeap{rightInd}))
                    rightOK = true;
                else
                    rightOK = false;
                end

                if(~leftOK && ~rightOK) %if both child violate, swap with the largest
                    if(obj.compareKeys(obj.keyHeap{leftInd}, obj.keyHeap{rightInd}))
                        rightOK = true;
                    else
                        leftOK = true;
                    end
                end

                if(leftOK && rightOK)
                    break; %heap is OK
                elseif(rightOK)
                    obj.swapKeys(pivotInd, leftInd);
                    pivotInd = leftInd; %continue down on left child
                else
                    obj.swapKeys(pivotInd, rightInd);
                    pivotInd = rightInd; %continue down on right child
                end
            end
        end

        function retKey = top(obj)
            retKey = obj.keyHeap{1};
        end

        function retSize = size(obj)
            retSize = obj.memberCount;
        end
    end

    methods
        function r = getParentOf(~, ind)
            if(ind < 2)
                r = -1;
                return;
            end
            r = floor(ind/2);
        end

        function r = getLeftChildOf(obj, ind)
            r = 2*ind;
            if(r > obj.memberCount)
                r = -1;
            end
        end

        function r = getRightChildOf(obj, ind)
            r = 2*ind + 1;
            if(r > obj.memberCount)
                r = -1;
            end
        end

        function swapKeys(obj, val1, val2)
            tempKey = obj.keyHeap{val1};
            obj.keyHeap{val1} = obj.keyHeap{val2};
            obj.keyHeap{val2} = tempKey;
        end
    end
end