CSC300: Priority Queues, Heaps, and Heapsort

Contents [0/6]

Notes from the textbook [1/6]
TestPQ [2/6]
FixedPQSortedIncreasing [3/6]
FixedPQSortedDecreasing [4/6]
FixedPQUnordered [5/6]
FixedPQHeap [6/6]

(Click here for one slide per page)


Notes from the textbook [1/6]

In these lectures I will use some notes from the textbook:

TestPQ [2/6]

file:PQ.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
package ds1.student.pq;

// This is a toy interface for Priority Queues
// You are not allowed to insert 0.0
public interface PQ {
    public int size();
    public boolean isEmpty();
    public void insert(double x);
    public double min();
    public double delMin();
    public void toGraphviz();
}

file:TestPQ.java [source]
01
02
03
04
05
06
07
08
09
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
package ds1.student.pq;

import stdlib.StdOut;
import stdlib.StdRandom;
import stdlib.Stopwatch;

import java.util.Scanner;

public class TestPQ {
    public static enum Order { INCREASING, DECREASING, RANDOM }
    public static void main(String[] args) {
        show(11, true, "1 4 3 6 8 5 11 10 7 9 2 - - 2"); // Example from text 
        show(9, true, "1 2 3 4 5 6 7 8 9 - - - - - - - -");
        show(9, true, "9 8 7 6 5 4 3 2 1 - - - - - - - -");
        showRandom(10, true);
        double prevInsert = 0;
        double prevDelMin = 0;
        for (int N = 128; N<=MAX; N += N) {
            timeTrial(N, Order.RANDOM);
            StdOut.format("N=%,13d Insert=%7.3f [%8.3f] DelMin=%7.3f [%8.3f]\n", N, timeInsert, timeInsert/prevInsert, timeDelMin, timeDelMin/prevDelMin);
            prevInsert = timeInsert;
            prevDelMin = timeDelMin;
        }
    }
    private static int MAX=200_000;
    private static PQ getPQ (int N) {
        return new FixedPQSortedIncreasing(N);
        //return new FixedPQSortedDecreasing(N);
        //return new FixedPQUnordered(N);
    }

    private static double timeInsert;
    private static double timeDelMin;
    private static void timeTrial(int N, Order order) {
        SHOW_STEPS=false;
        PQ pqTime = getPQ(N);                
        Stopwatch sw1 = new Stopwatch();
        for (int i=0; i<N; i+=1) {
            double item = StdRandom.uniform(1,N+1);
            switch (order) {
            case INCREASING: pqTime.insert (i); break; 
            case DECREASING: pqTime.insert(N-i); break; 
            case RANDOM: pqTime.insert (item); break;
            }
        }
        timeInsert = sw1.elapsedTime();

        Stopwatch sw2 = new Stopwatch();        
        for (int i=0; i<N; i+= 1) {
            pqTime.delMin();
        }    
        timeDelMin = sw2.elapsedTime();
    }

    public static boolean SHOW_STEPS=false;
    private static void showRandom (int N, boolean showSteps) {
        SHOW_STEPS=showSteps;
        PQ pq = getPQ(N);
        pq.toGraphviz();
        StdOut.format("               %s\n", pq);
        for (int i=0; i<4*N; i+=1) {
            if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) {
                double item = pq.delMin();
                StdOut.format("-%2.0f          : %s\n", item, pq);    
            } else {
                double item = StdRandom.uniform(10,100);
                pq.insert(item);
                StdOut.format("+%2.0f          : %s\n", item, pq);
            }
        }
        StdOut.println();
    }
    private static void show (int N, boolean showSteps, String input) {
        SHOW_STEPS=showSteps;
        Scanner s = new Scanner(input);
        PQ pq = getPQ(N);
        pq.toGraphviz();
        StdOut.format("               %s\n", pq);
        while (s.hasNext()) {
            String next = s.next();
            if ("-".equals(next)) { 
                double item = pq.delMin();
                StdOut.format("-%2.0f          : %s\n", item, pq);
            } else {
                double item = Integer.parseInt(next);
                pq.insert(item);
                StdOut.format("+%2.0f          : %s\n", item, pq);
            }
            pq.toGraphviz();
        }
        StdOut.println();
        s.close();
    }
}

file:FixedPQSortedIncreasing.java [source]
01
02
03
04
05
06
07
08
09
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
package ds1.student.pq;

import stdlib.StdOut;

import java.util.Arrays;

public class FixedPQSortedIncreasing implements PQ {
    private int N;
    private double[] a;
    
    public FixedPQSortedIncreasing(int capacity){ N = 0; a = new double[capacity+1]; }    
    public void toGraphviz()          { }
    public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
    public int size()                 { return N; }
    public boolean isEmpty()          { return N == 0; }
    
    public void insert(double x) {
        if (x == 0) throw new Error ("No zeroes allowed");
        if (N >= a.length-1) throw new Error("Overflow");
        N++;
        a[N] = x;
        for (int j = N; j > 1 && a[j] < a[j-1]; j--)
            exch2(j, j-1);
    }
    public double min() {
        return a[1];
    }
    public double delMin() {
        double result = a[1]; 
        for (int j = 2; j <= N; j++)
            exch(j, j-1);
        a[N] = 0.0;
        N--;
        return result;
    }
    private void exch(int i, int j) {
        double oldi = a[i];
        double oldj = a[j];
        a[i] = oldj;
        a[j] = oldi;
        if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
    }
    private void exch2(int i, int j) {
        double oldi = a[i];
        double oldj = a[j];
        if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
        a[i] = oldj;
        a[j] = oldi;
    }
    
    private boolean isSorted() {
        for (int i = 2; i < N; i++)
            if (a[i] < a[i-1]) return false;
        return true;
    }
}

file:FixedPQSortedDecreasing.java [source]
01
02
03
04
05
06
07
08
09
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
package ds1.student.pq;

import stdlib.StdOut;

import java.util.Arrays;

public class FixedPQSortedDecreasing implements PQ {
    private int N;
    private double[] a;
    
    public FixedPQSortedDecreasing(int capacity){ N = 0; a = new double[capacity+1]; }    
    public void toGraphviz()          { }
    public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
    public int size()                 { return N; }
    public boolean isEmpty()          { return N == 0; }
    
    public void insert(double x) {
        if (x == 0) throw new Error ("No zeroes allowed");
        if (N >= a.length-1) throw new Error("Overflow");
        N++;
        a[N] = x;
        for (int j = N; j > 1 && a[j] > a[j-1]; j--)
            exch2(j, j-1);
    }
    public double min() {
        return a[N];
    }
    public double delMin() {
        double result = a[N]; 
        a[N] = 0.0;
        N--;
        return result;
    }
    private void exch2(int i, int j) {
        double oldi = a[i];
        double oldj = a[j];
        if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
        a[i] = oldj;
        a[j] = oldi;
    }
}

file:FixedPQUnordered.java [source]
01
02
03
04
05
06
07
08
09
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
package ds1.student.pq;

import stdlib.StdOut;

import java.util.Arrays;

public class FixedPQUnordered implements PQ {
    private int N;
    private double[] a;
    
    public FixedPQUnordered(int capacity)  { N = 0; a = new double[capacity+1]; }    
    public void toGraphviz()          { }
    public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
    public int size()                 { return N; }
    public boolean isEmpty()          { return N == 0; }
    
    public void insert(double x) {
        if (x == 0) throw new Error ("No zeroes allowed");
        if (N >= a.length-1) throw new Error("Overflow");
        N++;
        a[N] = x;
    }
    private int minPosition() {
        if (N<=0) throw new Error("Underflow");
        int result = 1;
        for (int i=2; i<=N; i++) 
            if (a[i] < a[result]) result = i;
        return result;
    }
    public double min() {
        int m = minPosition(); 
        return a[m];
    }
    public double delMin() {
        int m = minPosition(); 
        double result = a[m];
        exch2(m, N);
        a[N] = 0.0;
        N--;
        return result;
    }
    private void exch2(int i, int j) {
        double oldi = a[i];
        double oldj = a[j];
        if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
        a[i] = oldj;
        a[j] = oldi;
    }
}

FixedPQSortedIncreasing [3/6]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
  public void insert(double x) {
    N++;
    a[N] = x;
    for (int j = N; j > 1 && a[j] < a[j-1]; j--)
      exch(j, j-1);
  }
  public double delMin() {
    double result = a[1]; 
    for (int j = 2; j <= N; j++)
      exch(j, j-1);
    a[N] = 0.0;
    N--;

    return result;
  }

Output

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
+ 3          : [ , 1, 3, 4, , , , , , , , ]
+ 6          : [ , 1, 3, 4, 6, , , , , , , ]
+ 8          : [ , 1, 3, 4, 6, 8, , , , , , ]
+ 5          : [ , 1, 3, 4, 5, 6, 8, , , , , ]
+11          : [ , 1, 3, 4, 5, 6, 8, 11, , , , ]
+10          : [ , 1, 3, 4, 5, 6, 8, 10, 11, , , ]
+ 7          : [ , 1, 3, 4, 5, 6, 7, 8, 10, 11, , ]
+ 9          : [ , 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]
+ 2          : [ , 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
- 1          : [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]
- 2          : [ , 3, 4, 5, 6, 7, 8, 9, 10, 11, , ]
+ 2          : [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]

N=          128 Insert=  0.004 [Infinity] DelMin=  0.002 [Infinity]
N=          256 Insert=  0.003 [   0.750] DelMin=  0.002 [   1.000]
N=          512 Insert=  0.001 [   0.333] DelMin=  0.002 [   1.000]
N=        1,024 Insert=  0.008 [   8.000] DelMin=  0.017 [   8.500]
N=        2,048 Insert=  0.003 [   0.375] DelMin=  0.010 [   0.588]
N=        4,096 Insert=  0.008 [   2.667] DelMin=  0.043 [   4.300]
N=        8,192 Insert=  0.023 [   2.875] DelMin=  0.130 [   3.023]
N=       16,384 Insert=  0.144 [   6.261] DelMin=  0.276 [   2.123]
N=       32,768 Insert=  0.352 [   2.444] DelMin=  1.091 [   3.953]
N=       65,536 Insert=  1.024 [   2.909] DelMin=  4.582 [   4.200]
N=      131,072 Insert=  4.022 [   3.928] DelMin= 16.941 [   3.697]

Insert is linear, DeleteMin is linear

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
  exch( 3, 4)> [ , 1, 4, 3, , , , , , , , ]
+ 3          : [ , 1, 3, 4, , , , , , , , ]
+ 6          : [ , 1, 3, 4, 6, , , , , , , ]
+ 8          : [ , 1, 3, 4, 6, 8, , , , , , ]
  exch( 5, 8)> [ , 1, 3, 4, 6, 8, 5, , , , , ]
  exch( 5, 6)> [ , 1, 3, 4, 6, 5, 8, , , , , ]
+ 5          : [ , 1, 3, 4, 5, 6, 8, , , , , ]
+11          : [ , 1, 3, 4, 5, 6, 8, 11, , , , ]
  exch(10,11)> [ , 1, 3, 4, 5, 6, 8, 11, 10, , , ]
+10          : [ , 1, 3, 4, 5, 6, 8, 10, 11, , , ]
  exch( 7,11)> [ , 1, 3, 4, 5, 6, 8, 10, 11, 7, , ]
  exch( 7,10)> [ , 1, 3, 4, 5, 6, 8, 10, 7, 11, , ]
  exch( 7, 8)> [ , 1, 3, 4, 5, 6, 8, 7, 10, 11, , ]
+ 7          : [ , 1, 3, 4, 5, 6, 7, 8, 10, 11, , ]
  exch( 9,11)> [ , 1, 3, 4, 5, 6, 7, 8, 10, 11, 9, ]
  exch( 9,10)> [ , 1, 3, 4, 5, 6, 7, 8, 10, 9, 11, ]
+ 9          : [ , 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]
  exch( 2,11)> [ , 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2]
  exch( 2,10)> [ , 1, 3, 4, 5, 6, 7, 8, 9, 10, 2, 11]
  exch( 2, 9)> [ , 1, 3, 4, 5, 6, 7, 8, 9, 2, 10, 11]
  exch( 2, 8)> [ , 1, 3, 4, 5, 6, 7, 8, 2, 9, 10, 11]
  exch( 2, 7)> [ , 1, 3, 4, 5, 6, 7, 2, 8, 9, 10, 11]
  exch( 2, 6)> [ , 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11]
  exch( 2, 5)> [ , 1, 3, 4, 5, 2, 6, 7, 8, 9, 10, 11]
  exch( 2, 4)> [ , 1, 3, 4, 2, 5, 6, 7, 8, 9, 10, 11]
  exch( 2, 3)> [ , 1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11]
+ 2          : [ , 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  exch( 2, 1)> [ , 2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  exch( 3, 1)> [ , 2, 3, 1, 4, 5, 6, 7, 8, 9, 10, 11]
  exch( 4, 1)> [ , 2, 3, 4, 1, 5, 6, 7, 8, 9, 10, 11]
  exch( 5, 1)> [ , 2, 3, 4, 5, 1, 6, 7, 8, 9, 10, 11]
  exch( 6, 1)> [ , 2, 3, 4, 5, 6, 1, 7, 8, 9, 10, 11]
  exch( 7, 1)> [ , 2, 3, 4, 5, 6, 7, 1, 8, 9, 10, 11]
  exch( 8, 1)> [ , 2, 3, 4, 5, 6, 7, 8, 1, 9, 10, 11]
  exch( 9, 1)> [ , 2, 3, 4, 5, 6, 7, 8, 9, 1, 10, 11]
  exch(10, 1)> [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 11]
  exch(11, 1)> [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1]
- 1          : [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]
  exch( 3, 2)> [ , 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, ]
  exch( 4, 2)> [ , 3, 4, 2, 5, 6, 7, 8, 9, 10, 11, ]
  exch( 5, 2)> [ , 3, 4, 5, 2, 6, 7, 8, 9, 10, 11, ]
  exch( 6, 2)> [ , 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, ]
  exch( 7, 2)> [ , 3, 4, 5, 6, 7, 2, 8, 9, 10, 11, ]
  exch( 8, 2)> [ , 3, 4, 5, 6, 7, 8, 2, 9, 10, 11, ]
  exch( 9, 2)> [ , 3, 4, 5, 6, 7, 8, 9, 2, 10, 11, ]
  exch(10, 2)> [ , 3, 4, 5, 6, 7, 8, 9, 10, 2, 11, ]
  exch(11, 2)> [ , 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, ]
- 2          : [ , 3, 4, 5, 6, 7, 8, 9, 10, 11, , ]
  exch( 2,11)> [ , 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, ]
  exch( 2,10)> [ , 3, 4, 5, 6, 7, 8, 9, 10, 2, 11, ]
  exch( 2, 9)> [ , 3, 4, 5, 6, 7, 8, 9, 2, 10, 11, ]
  exch( 2, 8)> [ , 3, 4, 5, 6, 7, 8, 2, 9, 10, 11, ]
  exch( 2, 7)> [ , 3, 4, 5, 6, 7, 2, 8, 9, 10, 11, ]
  exch( 2, 6)> [ , 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, ]
  exch( 2, 5)> [ , 3, 4, 5, 2, 6, 7, 8, 9, 10, 11, ]
  exch( 2, 4)> [ , 3, 4, 2, 5, 6, 7, 8, 9, 10, 11, ]
  exch( 2, 3)> [ , 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, ]
+ 2          : [ , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ]

FixedPQSortedDecreasing [4/6]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
  public void insert(double x) {
    N++;
    a[N] = x;
    for (int j = N; j > 1 && a[j] > a[j-1]; j--)
      exch(j, j-1);
  }
  public double delMin() {
    double result = a[N]; 


    a[N] = 0.0;
    N--;

    return result;
  }

Output

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 4, 1, , , , , , , , , ]
+ 3          : [ , 4, 3, 1, , , , , , , , ]
+ 6          : [ , 6, 4, 3, 1, , , , , , , ]
+ 8          : [ , 8, 6, 4, 3, 1, , , , , , ]
+ 5          : [ , 8, 6, 5, 4, 3, 1, , , , , ]
+11          : [ , 11, 8, 6, 5, 4, 3, 1, , , , ]
+10          : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ]
+ 7          : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ]
+ 9          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
- 1          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]
- 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]        

N=          128 Insert=  0.012 [Infinity] DelMin=  0.000 [     NaN]
N=          256 Insert=  0.008 [   0.667] DelMin=  0.000 [     NaN]
N=          512 Insert=  0.003 [   0.375] DelMin=  0.000 [     NaN]
N=        1,024 Insert=  0.032 [  10.667] DelMin=  0.001 [Infinity]
N=        2,048 Insert=  0.007 [   0.219] DelMin=  0.000 [   0.000]
N=        4,096 Insert=  0.015 [   2.143] DelMin=  0.000 [     NaN]
N=        8,192 Insert=  0.051 [   3.400] DelMin=  0.000 [     NaN]
N=       16,384 Insert=  0.138 [   2.706] DelMin=  0.000 [     NaN]
N=       32,768 Insert=  0.372 [   2.696] DelMin=  0.000 [     NaN]
N=       65,536 Insert=  1.359 [   3.653] DelMin=  0.000 [     NaN]
N=      131,072 Insert=  4.550 [   3.348] DelMin=  0.000 [     NaN]

Insert is linear, DeleteMin is constant

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
  exch( 4, 1)> [ , 1, 4, , , , , , , , , ]
+ 4          : [ , 4, 1, , , , , , , , , ]
  exch( 3, 1)> [ , 4, 1, 3, , , , , , , , ]
+ 3          : [ , 4, 3, 1, , , , , , , , ]
  exch( 6, 1)> [ , 4, 3, 1, 6, , , , , , , ]
  exch( 6, 3)> [ , 4, 3, 6, 1, , , , , , , ]
  exch( 6, 4)> [ , 4, 6, 3, 1, , , , , , , ]
+ 6          : [ , 6, 4, 3, 1, , , , , , , ]
  exch( 8, 1)> [ , 6, 4, 3, 1, 8, , , , , , ]
  exch( 8, 3)> [ , 6, 4, 3, 8, 1, , , , , , ]
  exch( 8, 4)> [ , 6, 4, 8, 3, 1, , , , , , ]
  exch( 8, 6)> [ , 6, 8, 4, 3, 1, , , , , , ]
+ 8          : [ , 8, 6, 4, 3, 1, , , , , , ]
  exch( 5, 1)> [ , 8, 6, 4, 3, 1, 5, , , , , ]
  exch( 5, 3)> [ , 8, 6, 4, 3, 5, 1, , , , , ]
  exch( 5, 4)> [ , 8, 6, 4, 5, 3, 1, , , , , ]
+ 5          : [ , 8, 6, 5, 4, 3, 1, , , , , ]
  exch(11, 1)> [ , 8, 6, 5, 4, 3, 1, 11, , , , ]
  exch(11, 3)> [ , 8, 6, 5, 4, 3, 11, 1, , , , ]
  exch(11, 4)> [ , 8, 6, 5, 4, 11, 3, 1, , , , ]
  exch(11, 5)> [ , 8, 6, 5, 11, 4, 3, 1, , , , ]
  exch(11, 6)> [ , 8, 6, 11, 5, 4, 3, 1, , , , ]
  exch(11, 8)> [ , 8, 11, 6, 5, 4, 3, 1, , , , ]
+11          : [ , 11, 8, 6, 5, 4, 3, 1, , , , ]
  exch(10, 1)> [ , 11, 8, 6, 5, 4, 3, 1, 10, , , ]
  exch(10, 3)> [ , 11, 8, 6, 5, 4, 3, 10, 1, , , ]
  exch(10, 4)> [ , 11, 8, 6, 5, 4, 10, 3, 1, , , ]
  exch(10, 5)> [ , 11, 8, 6, 5, 10, 4, 3, 1, , , ]
  exch(10, 6)> [ , 11, 8, 6, 10, 5, 4, 3, 1, , , ]
  exch(10, 8)> [ , 11, 8, 10, 6, 5, 4, 3, 1, , , ]
+10          : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ]
  exch( 7, 1)> [ , 11, 10, 8, 6, 5, 4, 3, 1, 7, , ]
  exch( 7, 3)> [ , 11, 10, 8, 6, 5, 4, 3, 7, 1, , ]
  exch( 7, 4)> [ , 11, 10, 8, 6, 5, 4, 7, 3, 1, , ]
  exch( 7, 5)> [ , 11, 10, 8, 6, 5, 7, 4, 3, 1, , ]
  exch( 7, 6)> [ , 11, 10, 8, 6, 7, 5, 4, 3, 1, , ]
+ 7          : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ]
  exch( 9, 1)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, 9, ]
  exch( 9, 3)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 9, 1, ]
  exch( 9, 4)> [ , 11, 10, 8, 7, 6, 5, 4, 9, 3, 1, ]
  exch( 9, 5)> [ , 11, 10, 8, 7, 6, 5, 9, 4, 3, 1, ]
  exch( 9, 6)> [ , 11, 10, 8, 7, 6, 9, 5, 4, 3, 1, ]
  exch( 9, 7)> [ , 11, 10, 8, 7, 9, 6, 5, 4, 3, 1, ]
  exch( 9, 8)> [ , 11, 10, 8, 9, 7, 6, 5, 4, 3, 1, ]
+ 9          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ]
  exch( 2, 1)> [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
- 1          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]
- 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]

FixedPQUnordered [5/6]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
  public void insert(double x) {
    N++;
    a[N] = x;


  }
  public double delMin() {              private int minPosition() {                          
    int m = minPosition();                int result = 1;                              
    double result = a[m];                 for (int i=2; i<=N; i++)                     
    exch(m, N);                             if (a[i] < a[result]) result = i;    
    a[N] = 0.0;                           return result;                               
    N--;                                }

    return result;
  }

Output

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
+ 3          : [ , 1, 4, 3, , , , , , , , ]
+ 6          : [ , 1, 4, 3, 6, , , , , , , ]
+ 8          : [ , 1, 4, 3, 6, 8, , , , , , ]
+ 5          : [ , 1, 4, 3, 6, 8, 5, , , , , ]
+11          : [ , 1, 4, 3, 6, 8, 5, 11, , , , ]
+10          : [ , 1, 4, 3, 6, 8, 5, 11, 10, , , ]
+ 7          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 9          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
+ 2          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, 2]
- 1          : [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
- 2          : [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 2          : [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, 2, ]

N=          128 Insert=  0.002 [Infinity] DelMin=  0.001 [Infinity]
N=          256 Insert=  0.000 [   0.000] DelMin=  0.001 [   1.000]
N=          512 Insert=  0.001 [Infinity] DelMin=  0.002 [   2.000]
N=        1,024 Insert=  0.000 [   0.000] DelMin=  0.005 [   2.500]
N=        2,048 Insert=  0.000 [     NaN] DelMin=  0.005 [   1.000]
N=        4,096 Insert=  0.001 [Infinity] DelMin=  0.010 [   2.000]
N=        8,192 Insert=  0.001 [   1.000] DelMin=  0.043 [   4.300]
N=       16,384 Insert=  0.002 [   2.000] DelMin=  0.109 [   2.535]
N=       32,768 Insert=  0.002 [   1.000] DelMin=  0.430 [   3.945]
N=       65,536 Insert=  0.002 [   1.000] DelMin=  2.089 [   4.858]
N=      131,072 Insert=  0.004 [   2.000] DelMin=  8.483 [   4.061]

Insert is constant, DeleteMin is linear

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
+ 3          : [ , 1, 4, 3, , , , , , , , ]
+ 6          : [ , 1, 4, 3, 6, , , , , , , ]
+ 8          : [ , 1, 4, 3, 6, 8, , , , , , ]
+ 5          : [ , 1, 4, 3, 6, 8, 5, , , , , ]
+11          : [ , 1, 4, 3, 6, 8, 5, 11, , , , ]
+10          : [ , 1, 4, 3, 6, 8, 5, 11, 10, , , ]
+ 7          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 9          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
+ 2          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, 2]
  exch( 1, 2)> [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, 2]
- 1          : [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
  exch( 2, 9)> [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
- 2          : [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 2          : [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, 2, ]

FixedPQHeap [6/6]

01
02
03
04
05
06
07
08
09
10
11
12
13
  public void insert(double x) {
    N++;
    a[N] = x;
    swim(N);
  }
  public double delMin() {
    double result = a[1];
    exch(1, N);
    a[N] = 0.0;
    N--;
    sink(1);
    return result;
  }

Output

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
+ 3          : [ , 1, 4, 3, , , , , , , , ]
+ 6          : [ , 1, 4, 3, 6, , , , , , , ]
+ 8          : [ , 1, 4, 3, 6, 8, , , , , , ]
+ 5          : [ , 1, 4, 3, 6, 8, 5, , , , , ]
+11          : [ , 1, 4, 3, 6, 8, 5, 11, , , , ]
+10          : [ , 1, 4, 3, 6, 8, 5, 11, 10, , , ]
+ 7          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 9          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
+ 2          : [ , 1, 2, 3, 6, 4, 5, 11, 10, 7, 9, 8]
- 1          : [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
- 2          : [ , 3, 4, 5, 6, 8, 9, 11, 10, 7, , ]
+ 2          : [ , 2, 3, 5, 6, 4, 9, 11, 10, 7, 8, ]

N=          128 Insert=  0.002 [Infinity] DelMin=  0.000 [     NaN]
N=          256 Insert=  0.001 [   0.500] DelMin=  0.000 [     NaN]
N=          512 Insert=  0.001 [   1.000] DelMin=  0.000 [     NaN]
N=        1,024 Insert=  0.000 [   0.000] DelMin=  0.000 [     NaN]
N=        2,048 Insert=  0.000 [     NaN] DelMin=  0.001 [Infinity]
N=        4,096 Insert=  0.001 [Infinity] DelMin=  0.002 [   2.000]
N=        8,192 Insert=  0.001 [   1.000] DelMin=  0.002 [   1.000]
N=       16,384 Insert=  0.003 [   3.000] DelMin=  0.004 [   2.000]
N=       32,768 Insert=  0.004 [   1.333] DelMin=  0.005 [   1.250]
N=       65,536 Insert=  0.005 [   1.250] DelMin=  0.012 [   2.400]
N=      131,072 Insert=  0.014 [   2.800] DelMin=  0.029 [   2.417]
N=      262,144 Insert=  0.013 [   0.929] DelMin=  0.053 [   1.828]
N=      524,288 Insert=  0.025 [   1.923] DelMin=  0.114 [   2.151]
N=    1,048,576 Insert=  0.051 [   2.040] DelMin=  0.280 [   2.456]
N=    2,097,152 Insert=  0.113 [   2.216] DelMin=  0.571 [   2.039]
N=    4,194,304 Insert=  0.201 [   1.779] DelMin=  1.402 [   2.455]
N=    8,388,608 Insert=  0.402 [   2.000] DelMin=  3.600 [   2.568]
N=   16,777,216 Insert=  0.822 [   2.045] DelMin=  8.440 [   2.344]
N=   33,554,432 Insert=  1.619 [   1.970] DelMin= 21.522 [   2.550]

Insert is logarithmic, DeleteMin is logarithmic

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 1, 4, , , , , , , , , ]
+ 3          : [ , 1, 4, 3, , , , , , , , ]
+ 6          : [ , 1, 4, 3, 6, , , , , , , ]
+ 8          : [ , 1, 4, 3, 6, 8, , , , , , ]
+ 5          : [ , 1, 4, 3, 6, 8, 5, , , , , ]
+11          : [ , 1, 4, 3, 6, 8, 5, 11, , , , ]
+10          : [ , 1, 4, 3, 6, 8, 5, 11, 10, , , ]
+ 7          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, , ]
+ 9          : [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
  exch( 2, 8)> [ , 1, 4, 3, 6, 8, 5, 11, 10, 7, 9, 2]
  exch( 2, 4)> [ , 1, 4, 3, 6, 2, 5, 11, 10, 7, 9, 8]
+ 2          : [ , 1, 2, 3, 6, 4, 5, 11, 10, 7, 9, 8]
  exch( 1, 8)> [ , 8, 2, 3, 6, 4, 5, 11, 10, 7, 9, 1]
  exch( 8, 2)> [ , 8, 2, 3, 6, 4, 5, 11, 10, 7, 9, ]
  exch( 8, 4)> [ , 2, 8, 3, 6, 4, 5, 11, 10, 7, 9, ]
- 1          : [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
  exch( 2, 9)> [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, 2, ]
  exch( 9, 3)> [ , 9, 4, 3, 6, 8, 5, 11, 10, 7, , ]
  exch( 9, 5)> [ , 3, 4, 9, 6, 8, 5, 11, 10, 7, , ]
- 2          : [ , 3, 4, 5, 6, 8, 9, 11, 10, 7, , ]
  exch( 2, 8)> [ , 3, 4, 5, 6, 8, 9, 11, 10, 7, 2, ]
  exch( 2, 4)> [ , 3, 4, 5, 6, 2, 9, 11, 10, 7, 8, ]
  exch( 2, 3)> [ , 3, 2, 5, 6, 4, 9, 11, 10, 7, 8, ]
+ 2          : [ , 2, 3, 5, 6, 4, 9, 11, 10, 7, 8, ]