要实现一个堆，有两个步骤：
- 1.找到最后一个非叶子节点
- 2.从后向前，对每个节点执行下潜
举例这里实现一个大顶堆
首先创建一个类
package com.dreams.heap;
/**
* 大顶堆
*/
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int capacity) {
this.array = new int[capacity];
}
}我们需要一个构造方法对传入的数组构造成堆
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}heapify()方法就是建堆逻辑
建堆第一步我们要找到最后一个非叶子节点
位置在size / 2 – 1，就是如图的5
然后就是建堆代码如下
// 建堆
private void heapify() {
// 找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
//下潜
down(i);
}
}找到最后这个非叶子节点 size / 2 – 1后，down()方法就是下潜，从后向前，对每个节点执行下潜
我们知道堆的特征是：
当 i>0 时，节点 i的父节点为 floor((i-1)/2)
在< size时，节点 i的左子节点为 2i+1，右子节点为 2i+2
如果从索引 1 开始存储节点数据
当 i > 1时，节点i的父节点为 floor(i/2)
down方法代码如下：
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
if (max != parent) { // 找到了更大的孩子
swap(max, parent);
//递归
down(max);
}
}swap就是一个简单的交换数据
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
构造方法初始化建堆后
删除堆顶元素
/**
* 删除堆顶元素
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}通过调用swap(0, size – 1)将堆顶元素与堆中的最后一个元素交换位置。这步骤是为了保持完全二叉树的结构，在移除堆顶元素后仍然保持这一结构。然后，调用down(0)方法对新的堆顶元素进行下沉操作，以恢复堆的性质。
注意这里没有真正输出只是size-1，删除元素放在后面。
获取堆顶元素
/**
* 获取堆顶元素
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
删除指定索引处元素
逻辑与删除堆顶元素类似
/**
* 删除指定索引处元素
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index,size - 1);
size--;
down(index);
return deleted;
}
替换堆顶元素
/**
* 替换堆顶元素
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
堆的尾部添加元素
/**
* 堆的尾部添加元素
* @param offered 新元素
* @return 是否添加成功
*/
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
// 将 offered 元素上浮
up(offered, size);
size++;
return true;
}逻辑在up函数，
- 方法开始时，将child初始化为要上浮元素的当前索引。在堆的尾部添加元素所以直接传入size。
- 循环条件是child > 0，意味着只要当前节点不是根节点（堆顶），就可能需要继续上浮。
- 在循环内部，首先计算当前节点的父节点索引parent = (child – 1) / 2。
- 接着，比较offered元素的值和其父节点的值。如果offered大于其父节点的值（符合最大堆性质），则说明offered需要继续上浮。此时，将父节点的值下移至当前节点位置，以为上浮留出空间。如果offered不大于其父节点的值，说明已找到正确的位置，跳出循环。
- 循环结束后，将offered放置在最终确定的位置上。
代码如下
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered, int index) {
int child = index;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
测试看看
public static void main(String[] args) {
int[] array = {2, 3, 1, 6, 4, 5};
MaxHeap heap = new MaxHeap(array);
System.out.println(Arrays.toString(heap.array));
heap.poll(4);
System.out.println(Arrays.toString(heap.array));
heap.replace(7);
System.out.println(Arrays.toString(heap.array));
}
注意这里没有真正输出只是size-1，删除元素放在后面。
那么堆排序的实现只要循环将堆头与尾交换，并size减1
public static void main(String[] args) {
int[] array = {2, 3, 1, 7, 6, 4, 5};
MaxHeap heap = new MaxHeap(array);
System.out.println(Arrays.toString(heap.array));
while (heap.size > 1) {
heap.swap(0, heap.size - 1);
heap.size--;
heap.down(0);
}
System.out.println(Arrays.toString(heap.array));
}
