堆数据结构是什么 如何构建最大堆

什么是堆数据结构

堆数据结构要满足2个条件：

1、是完全二叉树

2、树中的所有节点都遵循它们大于其子节点的属性，即最大元素位于根及其子节点且小于根节点，依此类推。这样的堆称为最大堆。相反，如果所有节点都小于其子节点，则称为最小堆

如何构建最大堆

为了从任何树构建一个最大堆，我们可以从下向上开始对每个子树进行堆，并在将函数应用于包括根元素在内的所有元素之后以一个最大堆结束。

在完整树的情况下，非叶节点的第一个索引由给出n/2-1。之后的所有其他节点都是叶节点，因此不需要堆化。

所以，我们可以构建一个最大堆为：

for(int i=n/2-1;i>=0;i--)
heapify(arr,n,i);