[数据结构与算法]数据结构--堆的操作

• 堆，是由优先队列而来的一种结构。
• 常常会有这种操作，删除一个集合中的最大或者最小元素，同时往集合中插入元素。
• 这种可以使用堆这种数据结构。像二叉树一样：但是树的根位置存放最大或者最小元素。
• 这种数据结构插入和删除的时间复杂度都是O(log₂n)，非常人性化

图我就不画了，这里附上最大堆的操作：

//最大堆的操作
//HeapStruct
typedef struct HeapStruct* MaxHeap;
struct HeapStruct
{
	ElementType* elements;
	int size;
	int capacity;
};
//创建一个堆
MaxHeap create(int MaxSize)
{
	MaxHeap H = malloc(sizeof(struct HeapStruct));
	H->elements = malloc((MaxSize + 1) * sizeof(ElementType));
	H->size = 0;
	H->capacity = MaxSize;
	H->elements[0] = MaxData;
	return H;
}

//往堆里插入一个元素
void insert(MaxHeap H, ElementType item)
{
	int i;
	if (isFull(H))
	{
		printf("MaxHeap is already full");
		return;
	}
	i = ++H->size;
	for (; H->elements[i/2] < item; i/=2)
		H->elements[i] = H->elements[i/2];
	H->elements[i] = item;
}
//删除堆的最大元素
ElementType deleteMax(MaxHeap H)
{
	int Parent, Child;
	ElementType MaxItem, temp;
	if (isEmpty(H)) { printf("MaxHeap is a empty"); return;}
	MaxItem = H->elements[1];
	temp = H->elements[H->size--];
	for (Parent =1; Parent*2 = H->size; Parent = Child)
	{
		Child = Parent * 2;
		if ((Child != H->size) && (H->elements[Child] < H->elements[Child +1]))
			Child++;
		if (temp >= H->elements[Child]) break;
		else
			H->elements[Parent] = H->elements[Child];
	}
	H->elements[Parent] = temp;
	return MaxItem;
}