东北大学842——排序的编程题

调整大根堆(只考过一次)

  1. 大根堆实际上还是数组
  2. 双亲结点,左孩子结点,右孩子结点为一组
  3. 先寻找最后的一组
  4. 每一次先比较两个孩子谁大
  5. 然后较大的孩子与双亲比较
    1. 双亲大,就跳到下一组,直到根
    2. 孩子大,交换孩子,双亲。
      1. 检查受改变的孩子的组有没有变
//根节点为1;递归的方式好写
void AdjustDown(int A[], int length, int i) {
        if(2i >= length) {
            return;
        }
        int maxChildIdx = 2i;
        if(2i+1 < length && A[2i] > A[2i+1]) {
                maxChildIdx = 2i+1;
        }
        if(A[i] >= A[maxChildIdx]) {
            return;
        }
        if(A[maxChildIdx] > A[i]) {
                A[0] = A[i];
                A[i] = A[maxChildIdx];
                A[maxChildIdx] = A[0];
        }
        AdjustDown(A, length, maxChildIdx);
}

void AdjustHeap(int A[], int length) {
    for(int i = length / 2;i > 0; --i) {
        AdjustDown(A, length, i);
    }
}
上一篇:数据结构和算法-堆


下一篇:Luogu P2612 [ZJOI2012]波浪