第6章优先队列（堆）

优先队列（堆）

 1 public class BinaryHeap<AnyType extends Comparable<? super AnyType>>
 2 {
 3     public BinaryHeap(){ this(DEFAULT_CAPACITY); }
 4     public BinaryHeap(int capacity)
 5     {
 6         currentSize = 0;
 7         array = (AnyType [])new Comparable[capacity + 1];
 8     }
 9 
10     public BinaryHeap(AnyType[] items)
11     {
12         currentSize = items.length;
13         array = (AnyType[])new Comparable[(currentSize + 2) * 11 / 10];
14 
15         int i = 1;
16         for (AnyType item : items)
17             array[i++] = item;
18         buildHeap();
19     }
20 
21     public void insert(AnyType x)
22     {
23         if (currentSize == array.length - 1)
24             enlargeArray(array.length * 2 + 1);
25 
26         int hole = ++currentSize;
27         for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2)
28             array[hole] = array[hole / 2];
29         array[hole] = x;
30     }
31 
32     private void enlargeArray(int newSize)
33     {
34         AnyType[] old = array;
35         array = (AnyType[])new Comparable[newSize];
36         for (int i = 0; i < old.length; i++)
37             array[i] = old[i];
38     }
39 
40     public AnyType findMin()
41     {
42         if (isEmpty())
43             throw new UnderflowException();
44         return array[1];
45     }
46 
47     public AnyType deleteMin()
48     {
49         if (isEmpty())
50             throw new UnderflowException();
51         AnyType minItem = findMin();
52         array[1] = array[currentSize--];
53         percolateDown(1);
54 
55         return minItem;
56     }
57 
58     private void buildHeap()
59     {
60         for (int i = currentSize / 2; i > 0; i--)
61             percolateDown(i);
62     }
63 
64     public boolean isEmpty(){ return currentSize == 0; }
65 
66     public void makeEmpty(){ currentSize = 0; }
67 
68     private static final int DEFAULT_CAPACITY = 10;
69 
70     private int currentSize;
71     private AnyType[] array;
72 
73     private void percolateDown(int hole)
74     {
75         int child;
76         AnyType tmp = array[hole];
77         for (; hole * 2 <= currentSize; hole = child)
78         {
79             child = hole * 2;
80             if (child != child && array[child + 1].compareTo(array[child]) < 0)
81                 child++;
82             if (array[child].compareTo(tmp) < 0)
83                 array[hole] = array[child];
84             else
85                 break;
86         }
87         array[hole] = tmp;
88     }
89 }

左式堆

 1 public class LeftistHeap<AnyType extends Comparable<? super AnyType>>
 2 {
 3     public LeftistHeap()
 4     { root = null; }
 5     
 6     public void merge(LeftistHeap<AnyType>rhs)
 7     {
 8         if (this == null)
 9             return;
10         root = merge(root, rhs.root);
11         rhs.root  = null;
12     }
13     
14     private Node<AnyType>merge(Node<AnyType>h1, Node<AnyType>h2)
15     {
16         if (h1 == null)
17             return h2;
18         if (h2 == null)
19             return h1;
20         if (h1.element.compareTo(h2.element) < 0) 
21             return merge1(h1,h2);
22         else
23             return merge1(h2, h1);
24     }
25     
26    private Node<AnyType>merge1(Node<AnyType>h1, Node<AnyType>h2)
27    {
28        if (h1.left == null) 
29            h1.left = h2;
30        else 
31        {
32            h1.right = merge(h1.right, h2);
33            if (h1.left.npl < h1.right.npl)
34                swapChildren(h1);
35            h1.npl = h1.right.npl + 1;
36        }
37        return h1;
38    }
39    
40    private static <AnyType> void swapChildren(Node<AnyType> t)
41    {
42        Node<AnyType> tmp = t.left;
43        t.left = t.right;
44        t.right = tmp;
45    }
46    
47    public void insert(AnyType x){ root = merge(new Node<>(x), root); }
48    
49    public AnyType findMin()
50    {
51        if (isEmpty())
52            throw new UnderflowException();
53        return root.element;
54    }
55    
56    public AnyType deleteMin()
57    {
58        if (isEmpty())
59            throw new UnderflowException();
60        
61        AnyType minItem = root.element;
62        root = merge(root.left, root.right);
63        
64        return minItem;
65    }
66    
67    public boolean isEmpty()
68    { return root == null; }
69    public void makeEmpty()
70    { root = null; }
71     
72    private static class Node<AnyType>
73    {
74        Node(AnyType theElement)
75        { this(theElement,null,null); }
76        
77        Node(AnyType theElement, Node<AnyType>lt, Node<AnyType>rt)
78        { element = theElement; left = lt; right = rt; npl = 0; }
79        
80        AnyType element;
81        Node<AnyType> left;
82        Node<AnyType> right;
83        int npl;
84    }
85    
86    private Node<AnyType> root;
87 }

二项队列

  1 public class BinomialQueue<AnyType extends Comparable<? super AnyType>>
  2 {
  3     public BinomialQueue()
  4     {
  5         theTrees = new BinNode[DEFAULT_TREES];
  6         makeEmpty();
  7     }
  8 
  9     public BinomialQueue(AnyType item)
 10     {
 11         currentSize = 1;
 12         theTrees = new BinNode[1];
 13         theTrees[0] = new BinNode<>(item, null, null);
 14     }
 15 
 16     private void expaneTheTrees(int newNumTrees)
 17     {
 18         BinNode<AnyType>[] old = theTrees;
 19         int oldNumTrees = theTrees.length;
 20 
 21         theTrees = new BinNode[newNumTrees];
 22         for (int i = 0; i < Math.min(oldNumTrees, newNumTrees); i++)
 23             theTrees[i] = old[i];
 24         for (int i = oldNumTrees; i < newNumTrees; i++)
 25             theTrees[i] = null;
 26     }
 27     
 28     public void merge(BinomialQueue<AnyType>rhs)
 29     {
 30         if (this == rhs)
 31             return;
 32         
 33         currentSize += rhs.currentSize;
 34         
 35         if (currentSize > capacity())
 36         {
 37             int newNumTrees = Math.max(theTrees.length, rhs.theTrees.length) + 1;
 38             expaneTheTrees(newNumTrees);
 39         }
 40         
 41         BinNode<AnyType>carry = null;
 42         for (int i = 0, j = 1; j <= currentSize; i++,j *= 2)
 43         {
 44             BinNode<AnyType>t1 = theTrees[i];
 45             BinNode<AnyType>t2 = i < rhs.theTrees.length ? rhs.theTrees[i] : null;
 46             
 47             int whichCase = t1 == null ? 0 : 1;
 48             whichCase += t2 == null ? 0 : 2;
 49             whichCase += carry == null ? 0 : 4;
 50             
 51             switch (whichCase)
 52             {
 53                 case 0:
 54                 case 1:
 55                     break;
 56                 case 2:
 57                     theTrees[i] = t2;
 58                     rhs.theTrees[i] = null;
 59                     break;
 60                 case 4:
 61                     theTrees[i] = carry;
 62                     carry = null;
 63                     break;
 64                 case 3:
 65                     carry = combineTrees(t1, t2);
 66                     theTrees[i] = rhs.theTrees[i] = null;
 67                     break;
 68                 case 5:
 69                     carry = combineTrees(t1, carry);
 70                     theTrees[i] = null;
 71                     break;
 72                 case 6:
 73                     carry = combineTrees(t2, carry);
 74                     theTrees[i] = null;
 75                     break;
 76                 case 7:
 77                     theTrees[i] = carry;
 78                     carry = combineTrees(t1, t2);
 79                     rhs.theTrees[i] = null;
 80                     break;
 81             }
 82         }
 83         for (int k = 0; k < rhs.theTrees.length; k++)
 84             rhs.theTrees[k] = null;
 85         rhs.currentSize = 0;
 86     }
 87     
 88     private BinNode<AnyType> combineTrees(BinNode<AnyType>t1, BinNode<AnyType>t2)
 89     {
 90         if (t1.element.compareTo(t2.element) > 0)
 91             return combineTrees(t2, t1);
 92         t2.nextSibling = t1.leftChild;
 93         t1.leftChild = t2;
 94         return t1;
 95     }
 96     
 97     public void insert(AnyType x){ merge(new BinomialQueue<>(x)); }
 98     
 99     public AnyType findMin()
100     {
101         if (isEmpty())
102             throw new UnderflowException();
103         
104         return theTrees[findMinIndex()].element;
105     }
106     
107     private int findMinIndex()
108     {
109         int i;
110         int minIndex;
111         
112         for (i = 0; theTrees[i] == null; i++)
113             ;
114         for (minIndex = i; i < theTrees.length; i++)
115             if (theTrees[i] != null && theTrees[i].element.compareTo(theTrees[minIndex].element) < 0 )
116                 minIndex = i;
117             
118         return minIndex;
119     }
120     
121     private AnyType deleteMin()
122     {
123         if (isEmpty())
124             throw new UnderflowException();
125         
126         int minIndex = findMinIndex();
127         AnyType minItem = theTrees[minIndex].element;
128         
129         BinNode<AnyType>deletedTree = theTrees[minIndex].leftChild;
130         
131         BinomialQueue<AnyType>deletedQueue = new BinomialQueue<>();
132         deletedQueue.expaneTheTrees(minIndex);
133         
134         deletedQueue.currentSize = (1 << minIndex ) - 1;
135         
136         for (int j = minIndex - 1; j >= 0; j--)
137         {
138             deletedQueue.theTrees[j] = deletedTree;
139             deletedTree = deletedTree.nextSibling;
140             deletedQueue.theTrees[j].nextSibling = null;
141         }
142         
143         theTrees[minIndex] = null;
144         currentSize -= deletedQueue.currentSize - 1;
145         
146         merge(deletedQueue);
147         
148         return minItem;
149     }
150 
151     public boolean isEmpty(){ return currentSize == 0; }
152 
153     public void makeEmpty()
154     {
155         currentSize = 0;
156         for (int i = 0; i < theTrees.length; i++)
157             theTrees[i] = null;
158     }
159 
160     private static class BinNode<AnyType>
161     {
162         BinNode(AnyType theElement)
163         { this(theElement, null, null); }
164         BinNode(AnyType theElement, BinNode<AnyType>lt, BinNode<AnyType>nt)
165         { element = theElement; leftChild = lt; nextSibling = nt; }
166 
167         AnyType element;
168         BinNode<AnyType> leftChild;
169         BinNode<AnyType> nextSibling;
170     }
171 
172     private static final int DEFAULT_TREES = 1;
173 
174     private int currentSize;
175     private BinNode<AnyType>[] theTrees;
176 
177     private int capacity(){ return ( 1 << theTrees.length ) - 1; }
178 }

第6章 优先队列（堆）

第6章优先队列（堆）