算法 之 堆 - 插入和删除

1. 插入

为了把元素x插入到堆H中，先将堆大小加1，然后将x添加到H的末尾，再根据需要，把x上移，直到满足堆特性。

如果n是新堆的大小，那么堆树的高度是⌊log n⌋，所以将一个元素插入大小为n的堆中所需要的时间是O(log n)。

 

过程  Insert

输入  堆H[1...n]和元素x

输出  新的堆H[1...n+1]，x为其元素之一

 

算法描述

n ← n+1 {增加H的大小}

H[n] ← x

Sift-up(H, n)

 

注意这里算法描述的数组的索引都是1...n，而不是大家习惯的0...n-1。

// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]  
// 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作 
int* insertElement(int* heap, int element)
{
	int heapLength = heap[0];
	int resultHeapLength = heapLength + 1;

	// 创建一个长度为resultHeapLength+1的int数组
	int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));
	if (resultHeap == NULL)
		return NULL;

	resultHeap[0] = resultHeapLength;
	for (int i = 1; i <= heapLength; i++)
	{
		resultHeap[i] = heap[i];
	}

	resultHeap[resultHeapLength] = element;
	siftUp(resultHeap, resultHeapLength);

	return resultHeap;	
}

 

2. 删除

要从大小为n的堆H中删除元素H[i]，可先用H[n]替换H[i]，然后将堆栈大小减1，如果需要的话，根据H[i]的键值与存储在它父节点和子节点中元素键值的关系，对H[i]做Sift-up或Sift-down运算，直到满足堆特性为止。

堆树的高度是⌊log n⌋，所以从一个大小为n的堆栈中删除一个元素所需要的时间是O(log n)。

 

过程  Delete

输入  非空堆H[1...n]和位于1和n之间的索引i

输出  删除H[i]之后的新堆H[1...n-1]

 

算法描述

x  ← H[i]; y ← H[n]

n ← n-1 {减小H的大小}

if i = n+1 then exit {完成}

H[i] ← y

if key(y) ≥ key(x) then Sift-up(H, i)

else Sift-down(H, i)

end if

 

注意这里算法描述的数组的索引也都是1...n，而不是大家习惯的0...n-1。

// heap[0]用来存储数组中堆数据的长度，堆数据heap[1]...heap[heapLength]  
// 所以数组的实际长度是heapLength+1，我们只对从数组索引为1开始的heapLength个数据进行操作 
int* deleteElement(int* heap, int index)
{
	int heapLength = heap[0];
	if (index < 1 || index > heapLength)
		return heap;

	int x = heap[index];
	int y = heap[heapLength];

	int resultHeapLength = heapLength - 1;

	// 创建一个长度为resultHeapLength+1的int数组
	int* resultHeap = (int*)malloc(sizeof(heap) * (resultHeapLength + 1));
	if (resultHeap == NULL)
		return NULL;

	resultHeap[0] = resultHeapLength;
	for (int i = 1; i <= resultHeapLength; i++)
	{
		resultHeap[i] = heap[i];
	}

	if (index == resultHeapLength)
		return resultHeap;

	resultHeap[index] = y;
	if (y > x)
	{
		siftUp(resultHeap, index);
	}
	else
	{
		siftDown(resultHeap, index);
	}

	return resultHeap;
}

 

我使用的数组是这样定义的：

const int HEAP_LENGH = 10;
int heap[HEAP_LENGH + 1] = { HEAP_LENGH, 20, 11, 9, 10, 5, 4, 5, 3, 7, 3 };

// 如果用我上面写的方法插入删除数据，不要忘了在操作完成之后释放内存哦
int* heapAfterInsert = insertElement(heap, 30);
int* heapAfterDelete = deleteElement(heapAfterInsert, 2);
free(heapAfterDelete);
free(heapAfterInsert);

 

更多内容请参考：

算法 之 堆 - 简介

算法 之 堆 - Sift-up和Sift-down