简述

首先堆又被称为完全二叉堆，因为它是一种逻辑上基于完全二叉树，物理上基于线性数据结构(如数组，链表等)的数据结构，堆根据其有序性可以被分为两种：大根堆(最大堆)-大根堆在逻辑上二叉树结构中满足根节点>子节点，小根堆(最小堆)-小根堆在逻辑上二叉树结构满足根节点<子节点

常见应用

利用堆的性质找出一个序列中最大最小的元素
堆排序
建立优先级队列，快速获取队列中优先级最高
在n个元素中排出前k大元素的问题，可以建立一个小根堆，依次读入n个元素并调整，当堆的规模达到k+1时，剔除第一个元素，剩下k个较大元素，保持堆的规模不超过k，然后一直循环

具体操作

下面介绍的操作以大根堆为例

堆的插入

每次插入都先将新数据放在数组最后，由于从这个新数据的父节点到根节点必然为一个有序的序列，在插入后，我们需要从下而上依次比较使堆整体有序，比如我们有这样一个堆数组[10,7,2,5,1]，下面我们往这个堆插入16，具体流程图如下

堆的删除

堆中删除需要把最后一个数据的值赋给根节点，然后再从根节点开始开始从上而下的调整，再从根节点开始进行一次从上向下调整，不断将根节点与其子节点比较调整直到堆恢复有序，下面，我们还是以堆数组[10,7,2,5,1]为例，下面我们删除10，具体流程图如下

堆的实现代码

由于最近在学python，所以使用python代码实现，其他版本请百度,同时，因为最大堆和最小堆实现方式类似，下面我们只给出最大堆代码

class Array(object):
    """
    Achieve an Array by Python list
    """
    def __init__(self, size = 32):
        self._size = size
        self._items = [None] * size

    def __getitem__(self, index):
        """
        Get items
        :param index: get a value by index
        :return: value
        """
        return self._items[index]

    def __setitem__(self, index, value):
        """
        set item
        :param index: giving a index you want to teset
        :param value: the value you want to set
        :return:
        """
        self._items[index] = value

    def __len__(self):
        """
        :return: the length of array
        """
        return self._size

    def clear(self, value=None):
        """
        clear the Array
        :param value: set all value to None
        :return: None
        """
        for i in range(self._size):
            self._items[i] = value

    def __iter__(self):
        for item in self._items:
            yield item
          
class MaxHeap(object):
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self._elements = Array(maxsize)
        self._count = 0

    def __len__(self):
        return self._count

    def add(self, value):
        if self._count >= self.maxsize:
            raise Exception('full')
        self._elements[self._count] = value
        self._count += 1
        self._siftup(self._count-1)  # 维持堆的特性

    def _siftup(self, ndx):
        if ndx > 0:
            parent = int((ndx-1)/2)
            if self._elements[ndx] > self._elements[parent]:    # 如果插入的值大于 parent，一直交换
                self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
                self._siftup(parent)    # 递归

    def extract(self):
        if self._count <= 0:
            raise Exception('empty')
        value = self._elements[0]    # 保存 root 值
        self._count -= 1
        self._elements[0] = self._elements[self._count]    # 最右下的节点放到root后siftDown
        self._siftdown(0)    # 维持堆特性
        return value

    def _siftdown(self, ndx):
        left = 2 * ndx + 1
        right = 2 * ndx + 2
        # determine which node contains the larger value
        largest = ndx
        if (left < self._count and     # 有左孩子
                self._elements[left] >= self._elements[largest] and
                self._elements[left] >= self._elements[right]):  # 原书这个地方没写实际上找的未必是largest
            largest = left
        elif right < self._count and self._elements[right] >= self._elements[largest]:
            largest = right
        if largest != ndx:
            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
            self._siftdown(largest)


def test_maxheap():
    import random
    n = 5
    h = MaxHeap(n)
    for i in range(n):
        h.add(i)
    for i in reversed(range(n)):
        assert i == h.extract()

Python中heapq模板

Python中创建一个堆可以直接使用list的创建方式H = [], 或者使用heapify()函数将一个存在的列表转为堆。

这个模块提供了下面几种堆的操作： heapq.heappush(heap, item) 往堆中插入一个值，同时要保持为最小堆。

heapq.heappop(heap) 返回堆中的最小值，并把它从堆中删除，同时保持为最小堆；如果堆为空，发生 IndexError。直接通过heap[0]可以获取最小值并不从堆中把它删除。

heapq.heappushpop(heap, item) 向堆中插入值后再弹出堆中的最小值，这个函数的速度比直接使用heappush() 和heappop()的效率更加高。

heapq.heapreplace(heap, item) 弹出和返回堆中的最小值再插入一个新的值。堆的大小没有改变。如果堆为空，产生 IndexError。这一个操作也比直接使用heappush() 和heappop()的效率更加高，尤其适合使用在固定堆大小不变的情况。与上一个函数相比，这个函数返回的值可能要比将要插入到堆的值大。

heapq.heapify(x) 将一个list转为最小堆，线性时间复杂度，O(n).

重要应用-堆排序

简述

堆排序主要分为两个步骤

建堆
- 升序：建大堆
- 降序：建小堆
利用堆删除的思想来排序，建堆和堆删除中都用到了向下调整，所以关键是要掌握向下调整下面以升序为例简述下堆排序的流程：

首先应该建一个大堆，不能直接使用堆来实现，可以将需要排序的数组看作是一个堆，但需要把数组结构变为堆
从堆倒数第二行最右边开始依次往下调整直到调整到堆顶，这样就可以把数组调整成一个堆
然后按照堆删的思想将堆顶域堆底的数据交换，不同的是这里不删除最后一个元素
这样一来最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大元素在堆顶，重复到只剩堆顶为止流程图如下：

实现代码

// 堆排序
void AdjustDown(int* a, int n, int root)//向下调整
{
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
	assert(a);
 
    //建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
    //交换
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);
		AdjustDown(a, i, 0);
	}
}

具体应用

给定数组{33,44,21,8,19,123,46,78,11}如何求解其第一趟堆排序后的结果？

总结

从上面的例子，我们可以看出，其实堆排序就是在树形结构下对父子节点不断进行交换，选出最大的放在堆顶，然后将对堆顶元素与堆底倒数第x个元素交换(x为当前循环趟数)，这样就起到了一趟选出一个剩余数组中最大值并放于剩余数组末尾的目的。它的特点是，一趟排序就能确定一个元素的最终位置，因为用了二叉树结构进行辅助排序，其时间复杂度显然为O(logn)

leetcode例题

6039-K次增加后的最大乘积

参考资料： OH,CGWLMXUP的博客西檬饭的博客风继续吹TT的博客

夏至的个人博客

数据结构-堆

简述