前言
大四重拾算法与数据结构，所有内容为自己的阶段小结所以并不是技术性文章，如有兴趣阅读，遇到问题不妨给我留个言，万分感谢！
堆
堆是一颗完全二叉树
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
构建堆
用到自己写的动态链表Array(附在后面)
package MaxHeap;
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
public MaxHeap() {
data = new Array<>();
}
public MaxHeap(E[] arr) {
data = new Array<>(arr);
}
public int getSize() {
return data.getSize();
}
public boolean isEmpty() {
return data.isEmpty();
}
private int parent(int index) {
if (index == 0)
throw new IllegalArgumentException("index 0 doesn't have parent!");
// 如果是重1开始计的话 则为index/2
return (index - 1) / 2;
}
private int leftChild(int index) {
// 如果是从1 开始计的话为 index * 2
return index * 2 + 1;
}
private int rightChil(int index) {
// 如果是从1开始计的话为 index * 2 + 1
return index * 2 + 2;
}
//每次从数组的最后一个位置开始插入 然后进行堆的重排序
//我们称这个过程为上浮操作
public void add(E e) {
data.addLast(e);
//从最后一个结点开始上浮
siftUp(data.getSize() - 1);
}
//元素的上浮操作
private void siftUp(int index) {
//如果这个结点大于自己的父节点 则交换两个结点
while(index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
data.swap(index, parent(index));
index = parent(index);
}
}
public E findMax() {
if(data.getSize() == 0)
return null;
return data.get(0);
}
//弹出最大数 也就是堆顶
public E extractMax() {
E ret = findMax();
//交换链表中的第一个数个最后一个数
data.swap(0, data.getSize() - 1);
//删除最后一个数 由于刚才交换之后 删除的数为堆的第一个数
data.removeLast();
//之后做下沉操作
siftDown(0);
return ret;
}
private void siftDown(int index) {
//找出下沉的结点左子树和右子树比较的最大值
while(leftChild(index) < data.getSize()) {
int j = leftChild(index);
if(j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
//data[j] 为leftChild 和 rightChild 中的最大值
if(data.get(index).compareTo(data.get(j)) >= 0)
break;
data.swap(index, j);
index = j;
}
}
}
Array
package MaxHeap;
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
public Array(E[] arr){
data = (E[])new Object[arr.length];
for(int i = 0 ; i < arr.length ; i ++)
data[i] = arr[i];
size = arr.length;
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resize(2 * data.length);
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contains(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return i;
}
return -1;
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0 ; i < size ; i ++){
res.append(data[i]);
if(i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
}
接下来是LeetCode关于堆的练习-347
package MaxHeap;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;
//Given a non-empty array of integers, return the k most frequent elements.
//返回出现评率最高的前k个数
/*
* 在Java中 PriorityQueue就是以个最小堆，所以存在堆顶的是元素中的最小值
* 我们可以把k个元素放在PriorityQueue中，把元素出现的次数当做排序的条件
* 然后每次进来的元素都和堆顶元素比较，如果大于堆顶的话我们插入，把堆顶弹出，并维护这个只有k个元素的堆
*/
public class LeetCode347 {
public List<Integer> topKFrequent(int[] nums, int k) {
//创建TreeMap 统计每个元素出现的个数
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
int count = map.getOrDefault(nums[i], 0);
map.put(nums[i], count + 1);
}
//创建优先队列 也就是最小堆 我们把元素出现的次数做为排序的原则
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//在创建优先队列的时候传入一个对象说明排序的原则
@Override
public int compare(Integer a, Integer b) {
//使用的就是元素出现的个数
return map.get(a) - map.get(b);
}
});
//维护k个元素的优先队列
for (int key : map.keySet()) {
if (pq.size() < k)
pq.add(key);
else if (map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
LinkedList<Integer> list = new LinkedList<>();
while (!pq.isEmpty()) {
list.add(pq.remove());
}
return list;
}
public static void main(String[] args) {
LeetCode347 test = new LeetCode347();
int nums[] = { 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3 };
System.out.println(test.topKFrequent(nums, 2));
}
}
