堆与堆排序

---

鸣谢：
https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.jianshu.com/p/21bef3fc3030

堆的定义：

具有以下性质的完全二叉树（结构很紧凑适合数组）：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

image.png

从大小层面看：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

从相对位置来说：

（i+1）/ 2 - 1=其顶部节点的位置

image.png

第一个非叶子结点下标为 len/2-1.

---

堆不能随意删除元素，只能删除根节点的元素。

---

堆的删除：（自顶向下）

删除堆顶元素然后替换为堆底元素：

image.png

length--然后进行下沉操作：

image.png

删除完成

// 删除操作，摘掉顶点元素，然后用a[length-1]替换，再边比较边下沉。
int del(struct Heap & heap){
  if(heap.length==0){
    return -1;
  }
  int pop=heap.heap[0];
  swap(heap.heap[0],heap.heap[heap.length-1]);
  heap.length--;

  if(heap.length==1){
      return pop;
  }
  else{
      int next=0;
      int root=0;
      // 让root遍历倒数第二层的节点，因为是完全二叉树，所以只有左右完整还有只有左子树两种情况。
      while(root<=(heap.length)/2-1){
        if(root*2+2<heap.length){
            if(heap.heap[root*2+1]>heap.heap[root*2+2]){
              next=root*2+1;
              if(next<heap.length){
                // 右子树可能为null！！！！需要检查再替换
                swap(heap.heap[next],heap.heap[root]);
              }
            }
            else{
              next=root*2+2;
              if(next<heap.length){
                // 右子树可能为null！！！！需要检查再替换
                swap(heap.heap[next],heap.heap[root]);
              }
            }
        }
        else if(heap.heap[root]>heap.heap[root*2+1]){
            next=root*2+1;
            swap(heap.heap[next],heap.heap[root]);
        }
        root=next;
      }
  }
  return pop;
}

---

堆的插入：（自底向上）

image.png

// 堆只需要满足a[i]>=a[i*2+1]&&a[i]>=a[i*2+2]
void build_heap(struct Heap &heap,int num){
  // 不加 & 会无法修改
  int foot,next;
  heap.heap[heap.length++]=num;
  foot=heap.length-1;
  //cout<<"----------------";
  while(foot>0){
    next=(foot+1)/2-1;
    // 大顶堆
    if(heap.heap[next]<heap.heap[foot]){
      swap(heap.heap[next],heap.heap[foot]);
    }
    else{
      break;
    }
    foot=next;
  }
};

---

排序的思路：

1. 无需序列构建成一个堆，将根据升序降序需求选择大顶堆或小顶堆
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

---

代码：

1. 构建一个堆：

// 从a[0]到a[length-1]逐个插入。
void build_heap(struct Heap &heap,int num){
  int root,next;
  heap.heap[heap.length++]=num;
  root=heap.length-1;
  //cout<<"----------------";
  while(root>0){
    next=(root+1)/2-1;
    // 大顶堆
    if(heap.heap[next]<heap.heap[root]){
      swap(heap.heap[next],heap.heap[root]);
    }
    root=next;
  }
}