二叉堆

二叉堆(Binary Heap)是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

堆的三个基本操作

堆关键是理解两个基本操作的实现：

1、向堆插入一个结点(上升操作)：

在堆尾（a[n]）插入一个元素，然后不断和父结点（a[i/2]）比较，如果比父结点大（大根堆]）或小（小根堆）就交换，一直到堆顶或不再交换就结束。 == 伪代码：

    '''proc up(i);
     begin
       while i>1 do ==
'''粗体文字'''
         begin
           j:=i div 2;
           if a[i]>a[j]''' then
             begin
               swap(a[i],a[j]);
               i:=j;
             end
           else
            break;
         end;'''''斜体文字''
     end;

(以上代码是大根堆的上升操作，小根堆只需将a[i]>a[j]改为a[i]<a[j]即可)

2、删除结点：

删除堆顶结点(下降操作)：

将堆顶结点（堆数组第一个）和堆尾结点（堆数组最后一个）交换，然后删除堆尾结点，将交换后的节点和左右儿子比较大小，然后选择两个儿子较大者（大根堆）或较小者（小根堆）再与节点进行比较大小，交换，更换节点编号，如此重复，直到满足堆的性质。

伪代码：(challenge: 这个哪里是伪代码？明明就是Pascal嘛）(再度challenge:PASCAL不就是伪代码吗......)

   proc down(i,n:longint);
    begin''
      while i<=n shr 1 do //因为a[n shr 1]的儿子就是a[n]了 {写给小白看的：因为i要与它的儿子比较并交换，所以这句话的目的是要保证i有儿子}
         begin
          j:=2*i;
          if (j+1<=n) and (a[j+1]>a[j]) then  //选择两个儿子中的较大者
             j:=j+1;
          if a[j]>a[i] then
            [[begin
              swap(a[i],a[j]);
              i:=j;
            end
          else
            break; 
        end;
    end;

]]

(以上代码是大根堆的下降操作，小根堆只需将所有的‘>'换为'<'即可)

不难得出，两个操作的复杂度都是O(log n)。

删除堆内结点：

如果要删除的结点是堆内结点，则需先判断是需要下降还是需要上升。

举一个简单的例子，有一个二叉堆：1 2 100 3 4 101 102 6，当我们需要删除101时，算法是：使用末尾替换需要删除的节点，首先尝试下降操作，如果无法下降，则尝试上升操作。

3.修改堆内元素的值

其实这也不算是基本操作，只是上升、下降操作的组合。

先看修改值之后节点是否能够上升，是则上升，反之则尝试下降。

 by dxc
 by Yarmu
 by Sky_Fall

堆排序

堆排序是堆的一个重要的应用，因为堆顶元素总是最大（大根堆）或最小（小根堆）的，所以根据这一性质，我们每次将堆顶元素与堆尾元素交换，并将堆的大小减一,再从堆顶元素做下降操作，如此重复，直到堆的大小变为1，这个时候,数组[1..n]已经为一个有序队列。

伪代码：

    //首先建堆
    for i:=n div 2 downto 1 do  //为什么从n div 2开始倒序呢？想想
      down(i,n);
   //排序过程
    for i:=n downto 2 do
      begin
        swap(a[1],a[i]);
        down(1,i-1);
      end;

可以得出堆排的时间复杂度约为O(n*logn)

注释程序{参考自clarkok的程序，部分注释by fys}

{By clarkok}
type
  heap = record                         // 小根堆
    h :array[1..100000] of longint;//记录元素的值
    c :longint;//记录堆的规模
  end;
 
var
  h:heap;
  n:longint;
  t:longint;
 
procedure swap(var a,b:longint);        // 交换 a和b
var
  t:longint;
begin
    t:=a;
    a:=b;
    b:=t;
end;
 
procedure up(pos:longint);               // 向上调整位于 pos的元素 维持堆的特性
begin
  while (pos>1) and (h.h[pos]<h.h[pos shr 1]) do// pos非根，且pos的值小于其父亲节点（pos div 2)则
    begin
      swap(h.h[pos],h.h[pos shr 1]);//交换pos和其父亲的值，小根堆的父亲节点为其儿子节点里最小的，既然插入的元素小于其父亲，那么其必然为父亲其旗下元素最小值，维护了堆的性质
      pos:=pos shr 1;//pos位置改为其父亲标号，调整完毕
    end;
end;
 
procedure down(pos:longint);               // 向下调整位于 pos的元素
var
  i,j:longint;
begin
  i:=pos;
  if i shl 1 + 1<=h.c then//其左、右儿子均存在
    begin
      if h.h[i shl 1] > h.h[i shl 1 + 1] then//找到其儿子里最小的那个
        j:=i shl 1 + 1
      else
        j:=i shl 1;
    end
  else//如果不是两个儿子均存在
  if i shl 1 <=h.c then//如果左儿子存在
    j:=i shl 1
  else
    exit;//都不存在
  while (h.h[j] < h.h[i]) do//儿子里娇小的小于要调整的元素的值就做
    begin
      swap(h.h[i],h.h[j]);//交换小的儿子和要调整的元素
      i:=j;
      if i shl 1 + 1<=h.c then//同上，判断有无儿子，最小儿子
        begin
          if h.h[i shl 1] > h.h[i shl 1 + 1] then
            j:=i shl 1 + 1
          else
            j:=i shl 1;
        end
      else
      if i shl 1 <=h.c then
        j:=i shl 1
      else
        exit;
    end;
end;//这样堆就维护完了
 
procedure add(x:longint);       // 将x加入堆
begin
  inc(h.c);//堆的规模+1；
  h.h[h.c]:=x;//把元素加到最后一个位置
  up(h.c);//向上调整元素位置
end;
 
function del(pos:longint):longint;  // 返回 位于 pos的元素值 并将其从堆中删除
begin
  del:=h.h[pos];//赋值
  swap(h.h[pos],h.h[h.c]);//交换删除元素处的值和堆的最后一个节点
  dec(h.c);//堆的规模-1
  down(pos);//调整pos处的堆，维护其堆的性质
end;
 
begin
  readln(n);
  for i:=1 to n do
  begin
    read(t);
    add(t);
  end;
  while h.c>0 do
    writeln(del(1));
end.

完整源码

C
Pascal
C++

二叉堆是一个小作品，欢迎帮助扩充这个条目。