数据结构-堆（heap）

大家好，我是讯享网，很高兴认识大家。

堆（heap）也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。如图一所示就是一个堆，堆优先顺序就是大的元素排在前面，小的元素排在后面，这样得到的堆称为最大堆。最大堆中堆顶的元素是整个堆中最大的，并且每一个分支也可以看成一个最大堆。同样的，我们可以定义最小堆，如图二所示。

这里写图片描述
讯享网
来源：http://blog.qiji.tech/archives/4855

堆的存储

堆可以看成一个二叉树，所以可以考虑使用二叉树的表示方法来表示堆。但是因为堆中元素按照一定的优先顺序排列，因此可以使用更简单的方法——数组——来表示，这样可以节省子节点指针空间，并且可以快速访问每个节点。堆得数组表示其实就是堆层级遍历的结果，如下图所示：

这里写图片描述
来源：http://rock3.info/blog/category/algorithm-and-data-structures/

这样对于每一个下标为i的节点，其左子节点在下标为2*i的位置，其右子节点在下标为2*i+1的位置，而其父节点在下标为 floor{i / 2}，其中i从1开始。通过数组的存储方式，可以通过计算下标，直接获取到相关节点。

typedef struct heap { int capacity; int size; int *arr; } Heap; #define MIN -1 Heap* CreateEmptyHeap (int max) { Heap *heap = (Heap*)malloc(sizeof(Heap)); if (heap == NULL) { printf("out of space!\n"); return NULL; } heap->capacity = max; heap->size = 0; heap->arr = (int*)malloc(sizeof(int) * (heap->capacity + 1)); heap->arr[0] = MIN; return heap; }

讯享网

以最小堆为例，说明堆得插入、删除等操作。

插入

堆还可以看成一个完全二叉树，每次总是先填满上一层，再在下一层从左往右依次插入。堆的插入步骤：

将新元素增加到堆的末尾
按照优先顺序，将新元素与其父节点比较，如果新元素小于父节点则将两者交换位置。
不断进行第2步操作，直到不需要交换新元素和父节点，或者达到堆顶
最后通过得到一个最小堆

通过将新元素与父节点调整交换的操作叫做上滤(percolate up)。

这里写图片描述
来源：http://blog.csdn.net/tuke_tuke/article/details/

讯享网Heap* Insert (Heap* heap, int val) { if (IsFull(heap)) { printf("heap is full!\n"); return heap; } // percolate up new element int i; for (i = ++heap->size; heap->arr[i] > val; i /= 2) heap->arr[i] = heap->arr[i/2]; heap->arr[i] = val; return heap; } bool IsFull (Heap* heap) { return (heap->capacity == heap->size); }

删除

堆的删除操作与插入操作相反，插入操作从下往上调整堆，而删除操作则从上往下调整堆。

删除堆顶元素（通常是将堆顶元素放置在数组的末尾）
比较左右子节点，将小的元素上调。
不断进行步骤2，直到不需要调整或者调整到堆底。

上述调整的方法称为下滤（percolate down）。
这里写图片描述
来源：http://blog.csdn.net/tuke_tuke/article/details/

bool IsEmpty (Heap* heap) { return (heap->size == 0); } Heap* DeleteMin (Heap* heap) { if (IsEmpty(heap)) { printf("empty heap!\n"); return NULL; } int minElement = heap->arr[1]; int lastElement = heap->arr[heap->size--]; int i, childIndex; for (i = 1; 2*i <= heap->size; i = childIndex) { childIndex = 2*i; //get the bigger child node if (heap->arr[childIndex] != heap->size && heap->arr[childIndex] > heap->arr[childIndex+1]) childIndex++; if (lastElement > heap->arr[childIndex]) heap->arr[i] = heap->arr[childIndex]; else break; } heap->arr[i] = lastElement; return heap; }

堆的存储

插入

删除

相关推荐