heapq简单介绍

堆特征：堆列表位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i 和 2 * i + 1处的元素）

api介绍

heapify(list) 让列表具有堆特征
heappush(heap, item) 将值压入堆中
heappop(heap) 从堆中弹出最小的元素
heapreplace(heap, item) 弹出最小的元素，并将值压入堆中
nlargest(n, iterable, key=None) 返回堆中n个最大的元素
nsmallest(n, iterable, key=None) 返回堆中n个最小的元素
heappushpop(heap, item) 将item压入堆中然后弹出最小的元素
merge(*iterables, key=None, reverse=False) 将有序序列进行合并排序，返回生成器序列

贪心算法使用

import collections
import heapq


def reorganizeString(S):
    c = collections.Counter(S).items()
    m = max(c, key=lambda x: x[1])[1]

    if m > (len(S) + 1) // 2:
        return ""

    if len(S) < 3:
        print(S)

    res = []
    x = [(-x[1], x[0]) for x in c]
    heapq.heapify(x)

    while len(x) > 1:
        c1, top1 = heapq.heappop(x)
        c2, top2 = heapq.heappop(x)
        res.extend([top1, top2])

        if c1 < -1:
            heapq.heappush(x, ((c1 + 1), top1))
        if c2 < -1:
            heapq.heappush(x, ((c2 + 1), top2))

    if x:
        res.append(x[0][1])

    return ''.join(res)


if __name__ == '__main__':
    print(reorganizeString('aab'))