之前我们实现的堆是创建一个数组，将元素组的内容拷贝过来进行排序的，这样的空间复杂度是O(N)，我们可对堆进行优化，使得不拷贝元素，直接在原数组上进行操作使得原数组变为有序的数组

堆的建立

向上调整建堆

//建堆——向上调整建堆 第一个元素看作一个堆，后面的元素看作依次插入
  for (int i = 1; i < n; ++i)
  {
  AdjustUp(a, i);
  }

向下调整建堆

之前向下调整的建堆方法是，头尾交换然后将头向下调整，向下调整的前提是左右子树都是大堆或小堆

当数组是这个样子。就无法使用向下调整

我们可以从倒数第一个非叶子节点（倒数第一个叶子节点的父节点）开始向下开始调，直到调整到根，叶子节点没必要调（兄弟关系），

先让i指向60，然后60和70交换，i--，i指向100再进行调整，之后再i--，i等于100进行调整

  //建堆——向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
    //物理上操作数组，逻辑上在操作堆
  {
    AdjusuDown(a, n, i);
  }

向上调整和向下调整时间复杂度的比较

向下调整时间复杂度：O（N） 向下调整总步数=该层个数*需向下调整次数 当满二叉树节点较多时，最后一层节点的个数约为总结点个数的一半，向下调整的好处：节点所在层数越小（以第1层为比较基准），调整次数越多，节点所在层数越大，此时节点越多，调整次数越小

向上调整时间复杂度：O(N*logN)

利用错位相减可计算出调整次数

我们只算最后一层的调整次数

向上调整：越往下节点越多，调整次数越多，算法时间复杂度过大

大小堆如何选择

对于升序和降序我们该如何选择建堆方式？

答案：1.升序——大堆     2.降序——小堆

大思路：选择排序，依次选数，从后往前排

升序建小堆会出问题

建堆的时间复杂度是O(N)，效率低

选数

//选数
  int i = 0;
  while (i < n)
  {
  Swap(&a[0], &a[n - i]);
  AdjusuDown(a, n - i, 0);
  ++i;
  }

void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
  HPDataTypedef minChild = parent * 2 + 1;
  while (minChild<n)
  {
  if (minChild+1<n&&a[minChild+1] >a[minChild])
  {
    minChild++;
  }
  if (a[minChild] > a[parent])
  {
    Swap(&a[parent], &a[minChild]);
    parent = minChild;
    minChild = parent * 2 + 1;
  }
  else
    break;
  }
}
void Heapsort(int* a, int n)
{
  //建堆——向下调整建堆
  for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
  //物理上操作数组，逻辑上在操作堆
  {
  AdjusuDown(a, n, i);
  }
  //选数
  int i = 1;
  while (i < n)
  {
  Swap(&a[0], &a[n - i]);
  AdjusuDown(a, n - i, 0);
  ++i;
  }
}
int main()
{
  int a[] = { 65,100,75,32,50,60 };
  Heapsort(a, 6);
  return 0;
}

Top-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能

数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

找前K个最大的

1.排序——O(N*logN)

2.堆选数

 a.建大堆和建小堆都可以，建大堆相当于选K次（Pop k次）时间复杂度：O(N+logN*k)