forked from hankcs/HanLP
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxHeap.java
More file actions
109 lines (99 loc) · 2.45 KB
/
MaxHeap.java
File metadata and controls
109 lines (99 loc) · 2.45 KB
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
/*
* <summary></summary>
* <author>He Han</author>
* <email>me@hankcs.com</email>
* <create-date>2015/11/22 13:23</create-date>
*
* <copyright file="MaxHeap.java" company="码农场">
* Copyright (c) 2008-2015, 码农场. All Right Reserved, http://www.hankcs.com/
* This source is subject to Hankcs. Please contact Hankcs to get more information.
* </copyright>
*/
package com.hankcs.hanlp.algorithm;
import java.util.*;
/**
* 用固定容量的优先队列模拟的最大堆，用于解决求topN大的问题
*
* @author hankcs
*/
public class MaxHeap<E> implements Iterable<E>
{
/**
* 优先队列
*/
private PriorityQueue<E> queue;
/**
* 堆的最大容量
*/
private int maxSize;
/**
* 构造最大堆
* @param maxSize 保留多少个元素
* @param comparator 比较器，生成最大堆使用o1-o2，生成最小堆使用o2-o1，并修改 e.compareTo(peek) 比较规则
*/
public MaxHeap(int maxSize, Comparator<E> comparator)
{
if (maxSize <= 0)
throw new IllegalArgumentException();
this.maxSize = maxSize;
this.queue = new PriorityQueue<E>(maxSize, comparator);
}
/**
* 添加一个元素
* @param e 元素
* @return 是否添加成功
*/
public boolean add(E e)
{
if (queue.size() < maxSize)
{ // 未达到最大容量，直接添加
queue.add(e);
return true;
}
else
{ // 队列已满
E peek = queue.peek();
if (queue.comparator().compare(e, peek) > 0)
{ // 将新元素与当前堆顶元素比较，保留较小的元素
queue.poll();
queue.add(e);
return true;
}
}
return false;
}
/**
* 添加许多元素
* @param collection
*/
public MaxHeap<E> addAll(Collection<E> collection)
{
for (E e : collection)
{
add(e);
}
return this;
}
/**
* 转为有序列表，自毁性操作
* @return
*/
public List<E> toList()
{
ArrayList<E> list = new ArrayList<E>(queue.size());
while (!queue.isEmpty())
{
list.add(0, queue.poll());
}
return list;
}
@Override
public Iterator<E> iterator()
{
return queue.iterator();
}
public int size()
{
return queue.size();
}
}