二叉堆
二叉堆的结构类似于二叉树
二叉堆的性质.png
二叉堆的代码实现
MaxHeap.java
package heap;
public class MaxHeap<E extends Comparable<E>> {
// 这里可以替换成Java的ArrayList，也可以用自己封装的类Array。
private Array<E> data;
public MaxHeap(int capacity) {
data = new Array<E>(capacity);
}
public MaxHeap() {
data = new Array<E>();
}
// 返回堆中的元素个数
public int size() {
return data.getSize();
}
// 返回一个布尔值，表示堆中是否为空
public boolean isEmpty() {
return data.isEmpty();
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index) {
if(index == 0)
throw new IllegalArgumentException("index-0 dosen't have parent.");
return (index - 1) / 2;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
private int leftChild(int index) {
return index * 2 + 1;
}
// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
private int rightChild(int index) {
return index * 2 + 2;
}
// 向堆中添加元素
public void add(E e) {
data.addLast(e); // 新加进来的元素就在数组末尾
siftUp(data.getSize() - 1); // 加入的最后一个元素执行上浮操作
}
// 传入需要上浮的节点的索引
private void siftUp(int k) {
// 节点不能是根节点
// 节点和父亲节点比较，如果比父亲节点大，就交换位置(交换值)
while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
// 交换之后，变换一下索引k，继续“往上”比较
data.swap(k, parent(k));
k = parent(k);
}
}
// 查看堆最大的元素
public E findMax() {
if(data.getSize() == 0)
throw new IllegalArgumentException("Can't not findMax when heap is empty!");
return data.get(0);
}
// 取出堆中的最大元素
public E extraceMax() {
E ret = findMax(); // 找到之后返回，并删除
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
/**
* SiftDown的逻辑
* 删除堆开头最大的元素之后，将最后一个元素放在开头
* 然后判断是否下沉
*/
private void siftDown(int k) {
// 极端情况，如果k已经没有子节点了。那就没有下沉的必要了
// 所以保持下沉，就必须先保证有（左）节点
// 也就是左节点的索引不超过范围
while (leftChild(k) < data.getSize()) {
// 获取左节点的索引
int j = leftChild(k);
// 判断有没有右节点，如果右节点比左节点大，交换
if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)
j = rightChild(k);
// 现在拿到的j就是左右两个节点最大的那个的索引
// 如果需要下沉的节点比根节点都大，就没有下沉的必要了，直接退出
if(data.get(k).compareTo(data.get(j)) >= 0)
break;
// 否则交换
data.swap(k, j);
k = j;
}
}
}
Array.java
package heap;
/**
* 动态数组
*
*/
public class Array<E> {
private E[] data;
private int size;
public Array() {
data = (E[]) new Object[10];
size = 0;
}
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
public int getSize() {
return this.size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
// 判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
// 在数组末插入元素，复用add
public void addLast(E e) {
add(size, e);
}
// 在数组头插入元素
public void addFirst(E e) {
add(0, e);
}
// 添加元素
public void add(int index, E e) throws IllegalArgumentException {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Illegal Argument, the index must be < 0 or > the size of the data");
}
if (data.length == size) {
// 扩容
resize(2 * data.length);
}
for (int i = size; i > index; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
public void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public E get(int index) {
// 这一步判断确保用户访问不到未初始化的元素
if (index < 0 || index >= size)
throw new IllegalArgumentException("Illegal Argument, the index must be < 0 or > the size of the data");
return data[index];
}
// 修改元素
public void set(int index, E e) {
// 这一步判断确保用户访问不到未初始化的元素
if (index < 0 || index >= size)
throw new IllegalArgumentException("Illegal Argument, the index must be < 0 or > the size of the data");
data[index] = e;
}
// 判断是否包含元素
public boolean contains(int e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e))
return true;
}
return false;
}
// 寻找元素的下标
public int find(int e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e))
return i;
}
return -1;
}
/**
* 根据下标删除元素
* 实现方式，和add相反
* 将index+1的元素赋值给index，index，size-1，使最后多余出来的sizeof(int)个字节不可访问
* <p>
* remove还欠缺缩容的算法
*/
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Illegal Argument, the index must be > 0 or < the size of the data");
E e = get(index);
for (int i = index; i < size - index - 1; i++) {
data[i] = data[i + 1];
}
// 如果检查到size<=capacity的1/2，就缩容为capacity的1/2;
// 为了防止复杂度震荡
// 当size == data.length / 4 才进行缩容操作
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
size--;
data[size] = null; // 优化
return e;
}
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;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public E getFirst() {
return get(0);
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append(String.format("Array: size = " + this.size + ", capacity：" + this.data.length + "\n"));
sb.append('[');
for (int i = 0; i < this.size; i++) {
sb.append(this.data[i]);
if (i != this.size - 1) {
sb.append(", ");
}
}
sb.append(']');
return sb.toString();
}
public static void main(String[] args) {
// Array<Integer> arr = new Array<>(20);
Array<Integer> arr = new Array<Integer>();// 默认初始化空间是10
System.out.println(arr);
for (int i = 0; i < 10; i++) {
arr.addLast(i);
}
System.out.println(arr);
// 插入第11个数据的时候，会扩容一倍
arr.addFirst(-1);
System.out.println(arr);
for (int i = 0; i < 6; i++) {
arr.removeLast();
}
System.out.println(arr);
arr.removeLast();
System.out.println(arr);
// arr.remove(0);
// System.out.println(arr);
// Array<Student> students = new Array<>(10);
// students.addFirst(new Student("xiaoming", 100));
// students.addLast(new Student("xiaobai", 99));
// students.addLast(new Student("xiaolv", 98));
// System.out.println(students);
// students.remove(1);
// System.out.println(students);
}
}
测试类Main.java
package heap;
import java.util.Random;
/**
* 堆加入元素的时候，会先放在数组最后位置
* 再根据上浮操作，安排好每一个元素的位置，
* 取出元素的时候只能将根节点的元素取出
* 根节点的元素比任何节点的元素都大
*/
public class Main {
public static void main(String[] args) {
int n = 1000000; // 插入一百万个数
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++)
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
// 保存在一个数组然后输出查看
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extraceMax();
}
for (int i = 1; i < n; i++)
if(arr[i - 1] < arr[i])
throw new IllegalArgumentException("Error");
System.out.println("Test MaxHeap completed.");
}
}
堆的时间复杂度.png
heapify操作
Array.java
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;
}
MaxHeap.java
/*
heapify
将任意数组替换成堆的结构
一种思路是扫描一遍数组中的元素，一个一个添加到堆里（时间复杂度O(nlogn)）
另外一种思路，从最后一个非叶子节点开始，往前每一个节点做SiftDown操作，时间复杂度O(n)
*/
public MaxHeap(E[] arr) {
data = new Array<>(arr);
for (int i = parent(arr.length - 1); i >= 0; i--)
siftDown(i);
}
