【数据结构】堆的建立（边输入数据边建立）（给定数字顺序插入）

堆的建立有两种方式，一个向上调整，一个向下调整，这两个得到的结果可能不同
- 向上调整一般用于边输入数据边建立，是给定数字顺序插入
- 向下调整一般是将所有结点先加入到一棵完全二叉树中，然后对二叉树的所有非叶子结点进行向下调整（从非叶子结点n/2开始，一直到1）

向上调整（大顶堆为例）：

void upAdjust(int i) {
  if(i == 1) return ;
  while(i != 1) {
    if(heap[i] > heap[i / 2]) {
    	swap(heap[i], heap[i / 2]);
    	i = i / 2;
    } else {
      break;
    }
  }
}

for(int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        upAdjust(i);
}

void upAdjust(int i) {

if(i == 1) return ;

while(i != 1) {

if(heap[i] > heap[i / 2]) {

swap(heap[i], heap[i / 2]);

i = i / 2;

} else {

break;

}

for(int i = 1; i <= n; i++) {

scanf("%d", &v[i]);

upAdjust(i);

}

向下调整（以大顶堆为例）：先将所有输入得到的数组存储到heap[i]中（构成了一颗完全二叉树，下标从1开始）

void createHeap() {
  for(int i = n / 2; i >= 1; i--)
    downAdjust(i, n);
}

void createHeap() {

for(int i = n / 2; i >= 1; i--)

downAdjust(i, n);

}

const int maxn = 100;
int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）
void downAdjust(int low, int high) {
  int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子
  while(j <= high) {
    if(j + 1 <= high && heap[j + 1] > heap[j])
      j = j + 1; //那就让j存储数值最大的那个结点所对应的下标
    if(heap[j] > heap[i]) {
      swap(heap[i], heap[j]);
      i = j; j = i * 2;
    } else {
      break;
    }
  }
}

const int maxn = 100;

int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）

void downAdjust(int low, int high) {

int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子

while(j <= high) {

if(j + 1 <= high && heap[j + 1] > heap[j])

j = j + 1; //那就让j存储数值最大的那个结点所对应的下标

if(heap[j] > heap[i]) {

swap(heap[i], heap[j]);

i = j; j = i * 2;

} else {

break;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版