基于动态数组(构建完全二叉树)实现最大堆并实现添加,替换,删除,取堆顶元素等操作
完全二叉树,通俗的理解就是,把元素一层一层的往下放,直到放不下位置,所以右下角有可能是空的,还缺少一些元素
二叉堆首先是一颗完全二叉树,除此之外它还有一个非常重要的性质,在堆中某个节点的值总是不大于其父节点的值,就是所有的父节点的值都大于等于它的孩子节点的值,这就是最大堆,反之就是最小堆
完全二叉树的特点其实就是一个个节点按顺序一层一层的放下来,所以可以用数组的方式来表示一颗完全二叉树,那么问题就来了,在数组中的每个节点,如何找到它的左右孩子是谁呢,仔细观察是存在如下规律的
parent (i) = i/2
left child (i) = 2 * i
right child (i) = 2 * i + 1
注意是整数除法,如果是奇数除以2,那么小数要被抹去
如果以下标0为起点,那么公式会发生以下改变:如图所示:
有了这个思路,就可以进行最大堆的实现:
在实现之前,附上所使用的动态数组实现:
/**
* @author BestQiang
*/
public class Array<E> {
private E[] data;
private int size;
/**
* 构造函数
*
* @param capacity 传入数组的容量
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 无参数的构造函数,默认数组的容量capacity=10
*/
public Array() {
this(10);
}
/**
* 构造参数传入一个数组,将其转换为动态数组(用于堆操作)
* @param arr
*/
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;
}
/**
* 获取数组中的元素个数
*
* @return
*/
public int getSize() {
return this.size;
}
/**
* 获取数组的容量
*
* @return
*/
public int getCapacity() {
return data.length;
}
/**
* 判断数组是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 向所有元素后添加一个元素
*
* @param e
*/
public void addLast(E e) {
/*if(size == data.length) {
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
data[size] = e;
size ++;*/
add(size, e);
}
/**
* 在所有数组前添加元素
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在第index个位置插入一个新元素e
*
* @param index
* @param e
*/
public void add(int index, E e) {
// 数组现在的长度等于声明长度,则说明数组已满,就对数组进行扩容
if (size == data.length) {
// throw new IllegalArgumentException("AddLast failed. Array is full.");
resize(2 * data.length);
}
// 如果要插入位置的索引小于0,或者大于现有数据(size代表插入数组末尾,如果插入位置大于size则数组会空)
// 注意因为是插入,所以允许插入size位置(size - 1的位置为末尾位置),而删除就不允许越过(size - 1)的位置
if (index < 0 || index > size) {
throw new IllegalArgumentException("AddLast failed. Require index >= 0 and index < size");
}
//从最后向前依次进行遍历,插入元素索引之后的元素进行后移,为插入元素腾出位置
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
//给对应索引的位置进行赋值
data[index] = e;
size++;
}
/**
* 获得index索引位置的元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get faild. Index is illegal");
}
return data[index];
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
// 修改index索引位置的元素为e
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e)
return true;
}
return false;
}
/**
* 查找指定索引的元素
*
* @param e
* @return
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素, 返回删除的元素
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get 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(内存泄漏)
//如果data的剩余长度低于总长度的四分之一且其长度不为零,就进行缩容
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
/**
* 从数组中删除第一个元素, 返回删除的元素
*
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
* 从数组中删除最后一个元素, 返回删除的元素
*
* @return
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 从数组汇总删除元素e
*
* @param e
*/
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Array: size = " + size + " , " + "capacity = " + data.length + "\n");
res.append("[");
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append("]");
return res.toString();
}
// 对数组进行扩容
private void resize(int newCapacity) {
// new一个newCpacity大小的新数组进行交接
E[] newData = (E[]) new Object[newCapacity];
// 利用for循环将原数组的数据转移至新数组
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
// 交换指定索引位置的两个元素的值
public void swap(int i, int j) {
if (i < 0 || i >= size || j < 0 || j >= size) {
throw new IllegalArgumentException("Index is illegal.");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
接下来基于动态数组实现最大堆:
/**
* @author BestQiang
*/
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);
// 就是找到最后一个节点的父节点,这个父节点也就是最后一个父节点,然后依次向前遍历,下沉较小的元素即可
for(int i = parent(arr.length - 1); i >= 0; i--)
siftDown(i);
}
// 返回堆中的元素个数
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 doesn'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) {
data.swap(k, parent(k));
k = parent(k);
}
}
// 看堆中的最大元素
public E findMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("Can not findMax when heap is empty");
}
return data.get(0);
}
// 取出堆中的最大元素
public E extractMax() {
//找到最大元素用于返回
E ret = findMax();
// 将堆顶元素与堆末元素进行位置交换
data.swap(0, data.getSize() - 1);
// 移除堆末元素
data.removeLast();
// 将堆顶元素沉到合适的位置
siftDown(0);
return ret;
}
// 思路:查找到堆顶元素的左右孩子,然后将堆顶元素与左右孩子的大小相比,如果比最大的还大,就符合要求,结束,
// 否则,将其与左右孩子中较大的进行位置互换,然后接下来一次类推
public void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
// 1.先找到右孩子索引
int j = leftChild(k);
// 2.将有孩子与做孩子比较,找出较大的然后与父亲比较
if (j + 1 < data.getSize() && data.get(j).compareTo(data.get(j + 1)) < 0) {
j = j + 1;
}
if(data.get(k).compareTo(data.get(j)) > 0) {
break;
} else {
//3. 如果父亲比孩子小就沉下去
data.swap(k, j);
//3. 将此时的孩子的位置赋值给k,进行下一次比较
k = j;
}
}
}
// 取出堆中最大的元素,并且替换成元素e
// 思路就是现在将堆顶元素替换为e,然后进行下沉
public E replace(E e) {
E res = findMax();
data.set(0, e);
siftDown(0);
return res;
}
}
对最大堆进行测试
import java.util.Random;
/**
* @author BestQiang
*/
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.extractMax();
}
// 如果数组中的元素不是从大到小排列的,则抛出异常
for (int i = 1; i < n; i++) {
if(arr[i-1] < arr[i]) {
throw new RuntimeException("Error");
}
}
System.out.println("Test MaxHeap completed.");
}
}
测试结果:
Test MaxHeap completed. 至此,最大堆实现完成,接下来可以使用最大堆实现优先队列
查看8道真题和解析
投递牛客等公司10个岗位 >