CSC300 / CSC402: Priority Queues, Heaps, and Heapsort

Contents [0/7]

Notes from the textbook [1/7]
TestPQ [2/7]
FixedPQSortedIncreasing [3/7]
FixedPQSortedDecreasing [4/7]
FixedPQUnordered [5/7]
FixedPQHeap [6/7]
Textbook Author's Code [7/7]

(Click here for one slide per page)


Notes from the textbook [1/7]

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

TestPQ [2/7]

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

// 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
 
package algs24;
import java.util.Scanner;
import stdlib.*;

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);
    MAX=50_000_000; return new FixedPQHeap(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
 
package algs24;
import stdlib.*;
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
 
package algs24;
import stdlib.*;
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
 
package algs24;
import stdlib.*;
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;
  }
}

file:FixedPQHeap.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
 
package algs24;
import stdlib.*;
import java.util.Arrays;

public class FixedPQHeap implements PQ {
  private int N;
  private double[] a;

  public FixedPQHeap(int capacity)  { N = 0; a = new double[capacity+1]; }  
  public void toGraphviz()          { GraphvizBuilder.binaryHeapToFile (a, N); }
  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;
    swim(N);
  }
  public double min() {
    if (N <= 0) throw new Error("Underflow");
    return a[1];
  }
  public double delMin() {
    double result = min();
    exch(1, N);
    a[N] = 0.0;
    N--;
    sink(1);
    return result;
  }

  private boolean isMinHeap() {
    for (int i = 2; i < N; i++)
      if (a[i] < a[i/2]) return false;
    return true;
  }
  // for comparison:
  private boolean isSorted() {
    for (int i = 2; i < N; i++)
      if (a[i] < a[i-1]) return false;
    return true;
  }

  private void swim(int k) {
    while (k > 1 && a[k/2] > a[k]) {
      int parent = k/2;
      exch2(k, parent);
      k = parent;
    }
  }
  private void sink(int k) {
    while (2*k <= N) {
      int left  = 2*k;
      int right = 2*k + 1;
      int child;
      if (right > N || a[left] < a[right]) 
        child = left;
      else 
        child = right;
      if (a[k] <= a[child]) break;
      exch2(k, child);
      k = child;
    }
  }
  private void sinkFromSlides(int k) {                
    while (2*k <= N) {                      
      int child = 2*k;                      
      if (2*k < N && a[2*k] > a[2*k+1])  
        child = 2*k + 1;
      if (a[k] <= a[child]) break;    
      exch2(k, child);                                    
      k = child;                                          
    }
    if (!isMinHeap()) throw new Error();
  }    
  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;
  }
}

FixedPQSortedIncreasing [3/7]

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/7]

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/7]

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/7]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
 
  public void insert(double x) {        private void swim(int k) {                
    N++;                                  while (k > 1 && a[k/2] > a[k]) {        
    a[N] = x;                               int parent = k/2;                     
    swim(N);                                exch2(k, parent);                     
                                            k = parent;                           
  }                                     } }                                       
  public double delMin() {              private void sink(int k) {                
    double result = a[1];                 while (2*k <= N) {                      
                                            int child = 2*k;                      
    exch(1, N);                             if (2*k+1 < N && a[2*k] < a[2*k+1])  
    a[N] = 0.0;                               child = 2*k + 1;
    N--;                                    if (a[k] < a[child]) break;    
    sink(1);                                exch2(k, child);                                    
    return result;                          k = child;                                          
  }                                     } }

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, ]

Textbook Author's Code [7/7]

Algorithms code, in algs24 package:

Notes: