# 堆 - heapify1

我们看一个堆里面相对比较重要的方法叫 heapify 翻译过来叫 (建堆，堆化)

这是什么意思呢？比如说我想做一个大顶堆，给了一个初始的数组

但是上面这个数组并不符合大顶堆的定义，因为大顶堆要求任意一个父节点它的值要比两个孩子节点大

我们要把上面这个数组调整成符合大顶堆的定义这个过程我们就叫做 heapify (建堆)

# 思路：

比如说准备了一个空堆我们向这个空堆中添加元素，如比我们先添加一个元素 2，如下图：

如果我们再加入一个元素 1 的话那么跟之前一样先跟父元素比较，如果比父元素小那么就符合条件加入到下面即可

如果我再加入一个元素 3 呢，这个 3 它比父元素大，这时我们就需要将父元素向下调整

调整下来后再跟它上上层的父元素进行比较，而此时并没有上上层元素了那么原本 p 指向的位置就是我们新加入元素正确的位置

那么把元素 3 添加到该位置就可以了

# Floyd 建堆算法作者 (也是之前龟兔赛跑判环作者)

# 算法描述:

找到最后一个非叶子节点 (什么是非叶子节点呢？就是有左右孩子的就是非叶子节点，叶子节点就是没有左右孩子的就跟树上的叶子一样)
1. 找到最后非叶子节点的公式：堆的大小 / 2 - 1 = 最后一个非叶子节点。注意：适用于数组索引从 0 为起点的
从后向前，对每个节点执行下潜

第一步找到非叶子节点那么在如下图中的非叶子节点就是 2, 3, 1 它要找的是最后一个非叶子节点那么就是 3

第二步从后向前也就是按 3， 2, 1 这个顺序从后向前然后为这每个节点执行下潜就可以了

# 演示过程：

第一步，我们在已经并不符合大顶堆特性的数组中找到最后一个非叶子节点那么就是 3

第二步，执行下潜，3 这个元素跟它两个较大的孩子进行交换，在这个例子中 7 更大那么就跟 3 交换位置 (下潜)

第三步，交换完之后 3 就没有更多的左右孩子了所以交换就停止了，这个下潜也就完成了

重复这个过程找到下一个最后的非叶子节点也就是 2

2 跟左右孩子进行比较跟较大的孩子进行交换位置 (下潜)

2 节点没有更多的做优孩子下潜就停止了

最后 1 进行跟左右孩子比较 7 更大，跟 7 交换位置 (下潜)

但是 1 还有更多的左右孩子，那么继续跟左右孩子比较较大的然后交换位置 (继续下潜)

1 潜到底就停止

到现在为止大顶堆就调整好了

# 代码实现：

	/**
	* @author Dkx
	* @version 1.0
	* @2024/1/2211:08
	* @function
	* @comment
	* 大顶堆
	*/
	public class MaxHeap
	{
	int array[];
	int size;

	public MaxHeap(int capacity)
	{
	this.array = new int[capacity];
	}

	/**
	* 如果实例化对象时传入的是一个普通数组那么我们就需要进行建堆让这个数组符合大顶堆的特性
	* @param array
	*/
	public MaxHeap(int array[])
	{
	// 将用户传入的数组赋值到成员变量中的数组
	this.array = array;
	// 更新数组的大小
	this.size = array.length;
	// 调用建堆方法进行建堆
	heapify();
	}

	// 建堆
	private void heapify()
	{
	// 如何找到最后这个非叶子节点 size / 2 - 1
	for(var i = size / 2; i >= 0; i--)
	down(i);
	}

	// 将 parent 索引处的元素下潜：与两个孩子较大者交换，直至没孩子或孩子没它大
	private void down(int parent)
	{
	// 通过公式获取当前节点的左孩子
	int left = parent * 2 + 1;
	// 通过上面公式 + 1 获取当前节点的右孩子
	int right = left + 1;
	// 假设当前节点是较大值
	int max = parent;
	// 在左孩子在合法索引范围内判断父节点的值是否小于左孩子，如果小就将左孩子的索引值赋值给 max 记录
	if(left < size && array[max] < array[left])
	max = left;
	// 在右孩子在合法索引范围内判断父节点的值是否小于右孩子，如果小就将右孩子的索引值赋值给 max 记录
	if(right < size && array[max] < array[right])
	max = right;
	// 如果上面两个判断中有一个满足了说明父节点不是最大值
	// 如果 max 被更改那么就不等于 parent 了说明右需要交换位置的
	if(max != parent)
	{
	// 让父节点和它左右孩子值较大的那个进行交换位置
	swap(max, parent);
	// 递归传入 max 也就是当前父节点的位置继续下一轮的判断
	down(max);
	}
	}

	// 交换两个索引处的元素
	private void swap(int i, int j)
	{
	int t = array[i];
	array[i] = array[j];
	array[j] = t;
	}
	}

计算机学科数据结构与算法堆 heapify