堆，二项队列，堆排序

ds 13 分钟 读完 (约 2012 字)

前言

从堆到二项队列到堆排序….当然都只是简单的堆。

二叉堆(Binary Heap)

堆也称优先队列，堆中的每个元素都有自己的权重，出堆操作会将 权重最小(或者最大) 的元素弹出。

二叉堆使用树来实现，树的根即堆顶，对于树的每一个节点，父亲的权重必然小于儿子的权重。下图即为一个堆(别问我为什么这么丑。。

堆

但实际上并不需要使用树来储存，可以用数组来实现，故而上图中实际上为(别问丑。。

堆在内存中

从上往下从左往右顺序存储在数组中。这种存储方式的性质为：heap[i]的儿子为heap[2*i]和heap[2*i+1](i从1开始，且儿子存在)，称为堆序性(heap order)

push

插入一个元素时，首先会找到数组的下一个空闲位置，将新元素放进去。然后，为了保持堆序性，将这个元素沿着其到根的路上滤(percolate up)，具体来说，便是swap(parent, child)，直到该位置能保持堆序性(此时元素的两个儿子都大于它)。

pop

弹出一个元素时，由于根即是最小元，所以弹出它。但是为了填充这个空穴，需要将它下滤(percolate down)，具体来说，便是将最后一个元素heap[size]放进这个空穴中(为什么不是size-1见下文)，然后swap(blank, less)，将空穴blank与其儿子中的较小者less交换，直到空穴的儿子都比它大。

实现

为了方便，将一个哑元(该哑元小于任何元素)放入heap[0]中，这样上滤一个最小元时便能因为heap[1]>heap[1/2]而停止上滤。故而堆的下标应该从1开始。

具体源码不再放出，具体见vegchic/learn-ds/heap.cpp，其中main()为测试函数

二项队列(Binary Queue)

普通二叉堆有一个弊端，合并困难(代价大)，故而需要更好的结构构建堆，书中讲述了左堆，斜堆，二项队列，这里实现了第三个(为啥不写左堆和斜堆呢，因为我忙(lan)啊

二项队列同样用树实现，但不同的是，它是树的集合，森林(forest)。里面的每一棵树也并非普通二叉树，而是二项树(binary tree)。在二项队列中，每一棵树的高度都不一样，高度为$k$的二项树由两棵高度为$k-1$的树合并而来，高度为$0$的树是一棵单节点树。

BTree

图即为$B_0, B_1, B_2, B_3$

实现时对每个节点结构，应有两个指针，一个指向儿子，一个指向兄弟。

btree

容易看出，任意的$N$都可以用2的幂相加得到(可看作二进制数)，所以二项队列可以表示任意堆。

push

由于二项队列核心是合并(Merge)，所以插入可以看做是size=1的二项队列与被插入队列合并。

pop

弹出时，应该遍历每一棵树的根，找出最小元所在的树(与二叉堆一样，每一棵树的最小元依然是根)，然后去掉该最小元，它的儿子便可以分成若干树，再将这些树合成一个新的二项队列，与原队列合并即可。

Merge

两个二项队列的合并操作归根到底是合并两棵相同高度的树，知道队列中不存在相同高度的树即可，这就好像二进制数的加法一样，每一位不是1就是0，如果两个1相加，就要往前面进位。所以在实现时也体现了进位的思想。

而相同高度的树合并，为了使根依然为最小元，所以将根小的作为母树，根大的作为子树附上去(这棵子树是根的第一个儿子，所以要把原先的儿子的地址添加到该子树的根的兄弟指针上)

类实现

在合并中，!!T1是当T1不为空时值为1，为空时值为0的表达式（可以说又让我这个菜鸡大开眼界了。另外，宏定义中MIN实际上是int类型的最大值，不过因为是用在找最小元上，所以就这样取名了(其实是因为MAX已经被占了，懒得改了

src

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#define MAX (32)
#define MIN (~0 ^ (1 << 31))
class binaryQueue {
  private:
    struct node {
      int ele;
      node *sibling;
      node *child;
      node(int i, node* s = 0, node* c = 0): ele(i), sibling(s), child(c) {}
      ~node() {
        if (sibling)
          delete sibling;
        if (child)
          delete child;
      }
    };

    int _size;
    node* roots[MAX];

    node* mergeSame(node *left, node *right) {
      if (right -> ele < left -> ele)
        return mergeSame(right, left);
      right -> sibling = left -> child;
      left -> child = right;
      return left;
    }
  public:
    binaryQueue(): _size(0) {
      memset(roots, 0, MAX * sizeof(binaryQueue*));
    }

    ~binaryQueue() {
      clear();
    }

    binaryQueue& push(int e) {
      node *newNode = new node(e);
      binaryQueue temp;
      temp.roots[0] = newNode;
      ++temp._size;
      merge(temp);
      return *this;
    }

    binaryQueue& merge(binaryQueue &heap) {
      if (heap._size + this -> _size > MIN) {
        cout << "Error!";
        return *this;
      }
      node *T1(0), *T2(0), *carry(0);
      int i(0), j(1);
      _size += heap._size;
      for ( ; j <= _size; j *= 2, ++i) {
        T1 = roots[i], T2 = heap.roots[i];
        switch(!!T1 + !!T2 * 2 + !!carry * 4) {
          case 0: //no trees
          case 1: //only T1
            break;
          case 2: //only T2
            roots[i] = T2;
            heap.roots[i] = 0;
            break;
          case 3: //T1 and T2
            carry = mergeSame(T1, T2);
            roots[i] = 0;
            heap.roots[i] = 0;
            break;
          case 4: //only carry
            roots[i] = carry;
            carry = 0;
            break;
          case 5: //T1 and carry
            carry = mergeSame(T1, carry);
            roots[i] = 0;
            break;
          case 6: //T2 and carry
            carry = mergeSame(T2, carry);
            heap.roots[i] = 0;
            break;
          case 7: //all
            roots[i] = carry;
            carry = mergeSame(T1, T2);
            heap.roots[i] = 0;
            break;
        }
      }
      return *this;
    }

    int pop() {
      if (_size == 0)
        return -1;
      int index = 0, min = MIN; 
      for (int i = 0, j = 1; j <= _size; ++i, j *= 2)
        if (roots[i] && roots[i] -> ele < min) {
          index = i;
          min = roots[i] -> ele;
        }
      node *deletedNode = roots[index];
      node *children = roots[index] -> child;
      roots[index] -> child = 0;
      delete roots[index];
      roots[index] = 0;
      binaryQueue deletedHeap;
      deletedHeap._size = (1 << index) - 1;
      for (int i = index - 1; i >= 0; --i) {
        deletedHeap.roots[i] = children;
        children = children -> sibling;
        deletedHeap.roots[i] -> sibling = 0;
      }
      roots[index] = 0;
      _size -= (deletedHeap._size + 1);
      merge(deletedHeap);
      return min;
    }

    int size() {
      return _size;
    }

    void clear() {
      for (int i = 0, j = 1; j <= _size; j *= 2, ++i) {
        if (roots[i])
          delete roots[i];
      }
    }

    int top() {
      if (_size == 0)
        return -1;
      int index = 0, min = MIN; 
      for (int i = 0, j = 1; j <= _size; ++i, j *= 2)
        if (roots[i] && roots[i] -> ele < min) {
          index = i;
          min = roots[i] -> ele;
        }
      return min;
    }
};

测试

自己测了一下，貌似没问题，然后就去leetcode随便找了道题做了下 leetcode23
leetcode23

时间有点慢。。因为要测试Merge()所以没想太多直接写了(说得好像想了就能快一样。顺便贴下Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        binaryQueue h;
        for (int i = 0; i < lists.size(); ++i) {
          binaryQueue tempHeap;
          ListNode* temp = lists[i];
          while (temp) {
            tempHeap.push(temp -> val);
            temp = temp -> next;
          }
          h.merge(tempHeap);
        }
        if (h.size() == 0)
            return 0;
        ListNode* res = new ListNode(h.pop());
        ListNode* temp = res;
        while (h.size() != 0) {
          temp -> next = new ListNode(h.pop());
          temp = temp -> next;
        }
        return res;
    }
};

堆排序($O(N\log N)$)

因为堆的特殊性质，便可以将之用于排序，对N个元素首先构建堆然后进行N次pop()操作。也可以用于解决选择问题（找出第几大的数。

如果使用一个额外的数组存储pop()的返回值，虽然不会显著增加运行时间，但会增加额外空间消耗。

因为每次pop()都会使数组$size-1$，所以可以将返回值放在堆尾，如果使用普通堆，得到的将是递减的数组，所以这里使用 (max)堆 (即每次都会弹出最大元)

src

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define leftChild(i) ((i) * 2 + 1)
class heapSort {
  private:
    void down(vector<int> &arr, int index, int size) {
      int ele = arr[index], child(0);
      for ( ; leftChild(index) < size; index = child) {
        child = leftChild(index);
        if (child + 1 < size && arr[child] < arr[child + 1])
          ++child;
        if (arr[child] > ele)
          arr[index] = arr[child];
        else
          break;
      }
      arr[child] = ele;
    }
  public:
    vector<int>& sort(vector<int> &arr) {
      if (arr.size() == 0)
        return arr;
      int size = arr.size();
      for (int index = size / 2; index >= 0; --index)
        down(arr, index, size);
      for (int index = size - 1; index > 0; --index) {
        int temp = arr[0];
        arr[0] = arr[index];
        arr[index] = temp;
        down(arr, 0, index);
      }
      return arr;
    }
};

Reference

雷打不动的《数据结构》以及Dadio

#algorithm #sort #heap
谈谈对Promise的小理解 排序II 归并排序与快速排序

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×