最大堆的Java实现

时间：2014-03-26 01:19:29 收藏：0 阅读：526
最大堆的解释见：http://www.java3z.com/cwbwebhome/article/article1/1362.html?id=4745
这里是整理后的代码：
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
 
import com.dm.core.structure.tupler.StrDoubleTuple;
 
/**
 * 最大堆，用作优先队列的TOPK查找<br>
 * 原理：每个节点的值都>=其左右孩子（如果有的话）值的完全二叉树
 * 
 * @author Anthony
 * @param <T>
 */
public 
class MaxHeap<T> {
 
    /**
     * 堆数据
     */
    private 
List<T> heap;
 
    /**
     * 堆数据的比较对象
     */
    private 
Comparator<T> comparator;
 
    public 
MaxHeap(List<T> heap) {
        this(heap, new 
Comparator<T>() {
            @SuppressWarnings("unchecked")
            @Override
            public 
int compare(T o1, T o2) {
                return 
((Comparable<T>) o1).compareTo(o2);
            }
        });
    }
 
    public 
MaxHeap(List<T> heap, Comparator<T> comparator) {
        super();
        this.heap = heap;
        this.comparator = comparator;
    }
 
    /**
     * 向最大堆中插入元素，添加到数组的尾部，然后上升操作
     * 
     * @param value
     */
    public 
void insert(T value) {
        // 数组下标为0的位置不放元素
        if 
(heap.size() == 0)
            heap.add(null);
        heap.add(value);
        up(heap.size() - 1);
    }
 
    /**
     * 节点上升递归实现<br>
     * 由于新插入的数是在数组尾部，所以需要做上升操作，让插入的数和父节点的值比较，当大于父节点的时候交换
     * 
     * @param index
     */
    private 
void up(int index) {
        // 注意堆是从下标为1开始，当index=1的时候，已经是根节点了
        if 
(index <= 1)
            return;
 
        int 
parent = index / 2; // 父节点
        T parentValue = heap.get(parent);
        T indexValue = heap.get(index);
        if 
(comparator.compare(parentValue, indexValue) < 0) {
            swap(parent, index);
            up(parent);
        }
    }
 
    /**
     * 节点上升非递归实现
     * 
     * @param index
     */
    @SuppressWarnings("unused")
    private 
void up2(int index) {
        int 
parent = 0;
        for 
(; index > 1; index /= 2) {
            parent = index / 2;
            T parentValue = heap.get(parent);
            T indexValue = heap.get(index);
            if 
(comparator.compare(parentValue, indexValue) < 0)
                swap(parent, index);
        }
    }
 
    /**
     * 交换a和b的位置
     * 
     * @param a
     * @param b
     */
    private 
void swap(int 
a, int b) {
        T temp = heap.get(a);
        heap.set(a, heap.get(b));
        heap.set(b, temp);
    }
 
    /**
     * 删除堆中位置是index处的值<br>
     * 原理是：当删除节点时，原来的位置就会出现一个孔，填充这个孔的方法就是，把最后的叶子赋给该孔，然后把该叶子删除
     * 
     * @param index
     */
    public 
void delete(int 
index) {
        heap.set(index, heap.get(heap.size() - 1));
        down(index);
        heap.remove(heap.size() - 1);
    }
 
    /**
     * 节点下沉递归实现<br>
     * 删除数据的时候，由于是用的尾部的数据（基本上是最小值）填充，所以需要做下沉操作
     * 
     * @param index
     */
    public 
void down(int 
index) {
        int 
n = heap.size() - 2; // 因为最后一个节点已经挪至index位置，所以已经是废弃叶子节点，不再考虑
        int 
child = 2 * index;
 
        // 说明该节点没有左右儿子节点了，那么无须下沉，直接返回
        if 
(child > n)
            return;
 
        // 如果左右儿子都存在，取值较大的那个儿子节点
        if 
(child < n
                && comparator.compare(heap.get(child), heap.get(child + 1)) < 0)
            child++;
 
        // 如果该节点小于较大的那个儿子，那么下沉
        if 
(comparator.compare(heap.get(index), heap.get(child)) < 0) {
            swap(child, index);
            down(child);
        }
    }
 
    /**
     * 节点下沉非递归实现
     * 
     * @param index
     */
    public 
void down2(int 
index) {
        T temp = heap.get(index);
        int 
n = heap.size() - 2;
        int 
child = 0;
        for 
(; 2 * index <= n; index = child) {
            child = 2 
* index;
            if 
(child < n
                    && comparator.compare(heap.get(child), heap.get(child + 1)) < 0)
                child++;
            if 
(comparator.compare(temp, heap.get(child)) < 0)
                swap(child, index);
            else
                break;
        }
    }
 
    /**
     * 根据树的性质建堆，树节点前一半一定是分支节点，即有孩子的，所以我们从这里开始调整出初始堆
     * 
     * @param heap
     */
    public 
void adjust() {
        for 
(int i = heap.size() / 2; i > 0; i--)
            adjust(i, heap.size() - 1);
    }
 
    /**
     * 调整堆，使其满足最大堆得定义<br>
     * 具体调整过程为: 从最后一个分支结点（n/2）开始，到根（1）为止，依次对每个分支结点进行调整（下沉）<br>
     * 以便形成以每个分支结点为根的堆，当最后对树根结点进行调整后，整个树就变成了一个堆
     * 
     * @param i
     * @param n
     */
    public 
void adjust(int 
i, int n) {
        int 
child = 0;
        for 
(; i <= n / 2;) {
            child = i * 2;
            if 
(child < n
                    && comparator.compare(heap.get(child), heap.get(child + 1)) < 0)
                child++;
            if 
(comparator.compare(heap.get(i), heap.get(child)) < 0) {
                swap(i, child);
                i = child; // 交换后，以child+1为根的子树不一定满足堆定义，所以从child处开始调整
            } else
                break;
        }
    }
 
    /**
     * 堆排序，从尾部开始，将每个节点和根节点交换，然后调整节点之上的子堆
     */
    public 
void sort() {
        for 
(int i = heap.size() - 1; i > 0; i--) {
            swap(1, i);
            adjust(1, i - 1);
        }
    }
 
    public 
static void main(String args[]) {
        List<Integer> array = new 
ArrayList<Integer>(Arrays.asList(null, 1, 2,
                5, 10, 3, 7, 11, 15, 17, 20, 9, 15, 8, 16));
        MaxHeap<Integer> mh = new 
MaxHeap<Integer>(array);
        mh.adjust();
        System.out.println("调整后的初始堆:" 
+ array);
        mh.delete(8);
        System.out.println("删除下标8之后的堆:" 
+ array);
        mh.insert(99);
        System.out.println("添加值99之后的堆:" 
+ array);
        mh.sort();
        System.out.println("排序后的堆:" 
+ array);
 
        List<StrDoubleTuple> list = new 
ArrayList<StrDoubleTuple>();
        list.add(null);
        list.add(new 
StrDoubleTuple("a", 1.0));
        list.add(new 
StrDoubleTuple("a", 2.0));
        list.add(new 
StrDoubleTuple("a", 5.0));
        list.add(new 
StrDoubleTuple("a", 10.0));
        list.add(new 
StrDoubleTuple("a", 3.0));
        list.add(new 
StrDoubleTuple("a", 7.0));
        list.add(new 
StrDoubleTuple("a", 11.0));
        list.add(new 
StrDoubleTuple("a", 15.0));
        list.add(new 
StrDoubleTuple("a", 17.0));
        list.add(new 
StrDoubleTuple("a", 20.0));
        list.add(new 
StrDoubleTuple("a", 9.0));
        list.add(new 
StrDoubleTuple("b", 15.0));
        list.add(new 
StrDoubleTuple("a", 8.0));
        list.add(new 
StrDoubleTuple("a", 16.0));
        MaxHeap<StrDoubleTuple> mho = new 
MaxHeap<StrDoubleTuple>(list);
        mho.adjust();
        System.out.println("调整后的初始堆:" 
+ list);
        mho.delete(8);
        System.out.println("删除下标8之后的堆:" 
+ list);
        mho.insert(new 
StrDoubleTuple("a", 99.0));
        System.out.println("添加值99之后的堆:" 
+ list);
        mho.sort();
        System.out.println("排序后的堆:" 
+ list);
    }
}
最大堆的Java实现,布布扣,bubuko.com
原文：http://www.cnblogs.com/AnthonyViking/p/3623529.html