44、如何在 O(n) 时间复杂度内构建一个堆？

1.什么是堆

堆是一种特殊的完全二叉树，分为大根堆和小根堆。满足父节点>子节点的点就是大根堆，满足父节点<子节点的就是小根堆。由此可知，大根堆堆顶元素最大，小根堆对顶元素最小

2.建堆的过程：从后遍历，向下调整，实现O(n)

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆。这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

即 从后往前遍历，从上往下调整（因为每次遍历的主体都是 非叶子节点）

//建立大堆
int arr[8]={23,12,32,5,27,8,35,16};

//向下调整的代码如下：

//size表示有多少个数据个数
//pos表示从那个位置(下标)开始向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
	//选出左右孩子中最大
	if (child + 1 < size && a[child + 1] > a[child])
	{
		++child;
	}
	if (a[child] > a[parent])
	{
		Swap(&a[child], &a[parent]);
		parent = child;
		child = parent * 2 + 1;
	}
	else
	{
		break;
	}
}
}
//向下调整建堆的代码如下：

int arr[8]={23,12,32,5,27,8,35,16};
int end=size-1;
for(int i=(end-1)/2;i>=0;i++)
{
AdjustDown(arr,size,i);

3.什么是堆排序？

堆排序是一种利用堆结构的排序方法，排序过程：

• 将无序数组构建成一个最大堆，堆顶元素就是最大元素
• 将堆顶元素（数组中最大元素）和数组最后一个元素交换，交换后数组中最大元素就在数组的最后一个位置
• 对于数组前n-1个元素，重新构建大根堆。经过n-1次交换和建堆后，得到升序数组

时间复杂度：O(n log n)，空间复杂度：O(1)（就地排序）

4.堆 与 优先级队列

底层原理

优先级队列的底层就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue（注意：默认情况下priority_queue是大堆）。优先级队列是默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将 元素构造成堆的结构

优先级队列的使用

priority_queue<typename, container, functional>

• typename是数据的类型；
• container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认用的vector；
• functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；
  • 如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。
  • 使用自定义的数据类型的时候，可以重写比较函数，也可以在自定义类型中进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小堆）。

功能接口

pop 与 push:
注意：在pop时，不能直接删除：

• 要先将第一个和最后一个元素交换，再删除最后一个位置（也就是之前最大的 那个元素）
• 然后为了保持原来的大堆/小堆结构，再走一次向下调整算法。

  void pop()//堆顶元素
  		{
  			swap(_con[0], _con[_con.size() - 1]);
  			_con.pop_back();
  			AdjustDown(0);
  		}

注意：push也不能只插入到里面就不管，为了防止破坏原来的结构，则需要走一次向上调整算法。

  void push(const T& x)
  		{
  			_con.push_back(x);_
  			AdjustUp(_con.size() - 1);
  		}

时间复杂度：插入和删除操作都是 O(log n)。