标签：lgn 堆排序 largest 导论 Heapify 算法 key Max 节点

维护堆

主要思想

• 比较 \(A[i],A[Left(i)]\) 和 \(A[Right(i)]\) 的大小
• 如果 \(A[i]\) 不是最大的，则将其与比较大的孩子节点进行交换
• 在堆中继续向下比较和交换，直到 \(i\) 节点为根的子树是一个大顶堆

伪代码

Max-Heapify(A, i, n) {
	l = Left(i);
  r = Right(i);
  if(l <= n && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= n && A[r] > A[largest]) largest = r;
  if(largest != i) {
  	swap(A[i], A[largest]);
    Max-Heapify(A, largest, n);
  }
}

运行时间为 \(O(lgn)\)，因为树的高度为 \(lgn\)，而将 \(A[i]\) 向下移动一层需要常数级时间。

建堆

主要思想

自底向上把一个无序的数组建成大顶堆。

• 在建堆的过程中，只需要考虑非叶节点
• 子数组 \(A[n/2+1,...,n]\) 中的元素对应的所有节点都是叶子结点

伪代码

Build-Max-Heap(A, n) {
	for(i = n/2; i >= 1; i--) {
  	Max-Heapify(A, i, n);
  }
}

效率分析

简单界：\(O(n)\) 调用 Max-Heapify，每次调用需要 \(O(lgn)\) 的时间，故建堆需要 \(O(nlgn)\) 时间。

准确界：堆的高度是 \(lgn\)

• 最多有 \(\lceil n/2^{h+1} \rceil\) 个高度为 \(h\) 的节点
• 在高度为 \(h\) 的节点上运行 Max-Heapify 的时间是 \(O(h)\)

因此建堆的总代价是：

\[\sum_{h=0}^{lgn}\lceil\frac{n}{2^{h+1}}\rceil{O(h)}=O(n\sum_{h=0}^{lgn}\frac{n}{2^h})\leq{O(n\sum_{h=0}^{\infty})h(\frac{1}{2})^h} \\ \sum_{k=0}^{\infty}x^k=\frac{1}{1-x} for |x|<1 \\ \Longrightarrow\sum_{k=0}^{\infty}kx^{k-1}=\frac{1}{(1-x)^2} \\ \Longrightarrow\sum_{k=0}^{\infty}kx^k=\frac{x}{(1-x)^2} \\ \Longrightarrow{O(n\sum_{h=0}^{\infty}h(\frac{1}{2})^h)}=O(2n)=O(n) \]

堆排序

主要思想

• 在数组上建立大顶堆
• 从根节点开始，将根节点与数组最后一个元素进行交换
• “去掉”数组中最后一个元素，然后在新的根节点上调用 Max-Heapify
• 重复上面两个步骤，直到只剩下一个节点

伪代码

HeapSort(A, n) {
	Build-Max-Heap(A, n);
  for(i = n; i > 1; i--) {
  	swap(A[1], A[i]);
    Max-Heapify(A, 1, i-1);
  }
}

效率分析

• 建堆：\(O(n)\)
• for 循环 \(n-1\) 次
  • swap ：\(O(1)\)
  • Max-Heapify：\(O(lgn)\)

故总时间为 \(O(nlgn)\)

优先队列

\(Increase-Key(A, i, key)\)：增加元素 \(i\) 的 \(key\)

• 确保 \(A[i]\leq{key}\)
• 更新 \(A[i]\) 的 \(key\)
• 向上遍历树，比较 \(A[i]\) 和它的父节点，有需要就交换值，直到 \(A[i]\) 的 \(key\) 比它的父节点小

Increase-Key(A, i, key) {
	if(key < A[i]) return;
  A[i] = key;
  while(i > 1 && A[Parent(i)] < A[i]) {
  	swap(A[i], A[Parent(i)]);
    i = Parent(i);
  }
}

时间：\(O(lgn)\)

\(Insert(A,key,n)\)：将元素 \(key\) 插入集合 \(A\)

• 增加堆的大小
• 在堆的最后一个位置增加一个 \(key\) 为 \(-\infty\) 的节点
• 增加 \(-\infty\) 到 \(key\)，调用 \(Increase-Key\)

Insert(A, key, n) {
	n = n + 1;
  A[n] = -inf;
  Increase-Key(A, n, key)
}

时间：\(O(lgn)\)

\(Extract-Max(A,n)\)：去掉并返回集合 \(A\) 中 \(key\) 最大的元素

• 确保堆不空
• 复制最大元素（根节点）
• 把树中最后一个节点变成新的根节点

Extract-Max(A, n) {
	if(n < 1) return;
  max = A[1];
  A[1] = A[n];
  n = n - 1;
  Max-Heapify(A, 1, n);
  return max;
}

时间：\(O(lgn)\)

标签：lgn,堆排序,largest,导论,Heapify,算法,key,Max,节点
From： https://www.cnblogs.com/fireonfire/p/17093970.html