堆

堆

一、概念

堆（Heap）是一类数据结构，它们拥有树状结构，且能够保证父节占比子节点大（或小）。当根节点保存堆中最大值时，称为大根堆反之，则称为小根堆。
二叉堆(BinaryHeap）是最简单、常用的堆，是一棵符合堆的性质的完全二叉树。它可以实现$O(lo{g}_{2}n)$地插入或删除某个值，并且$O(1)$地查询最大（或最小）值。

二、存储方式

作为一棵完全二叉树，二叉堆完全可以用一个$1$~$n$的数组来存储，对于节点p，，$p\ast 2$即为左儿子，$p\ast 2+1$即为右节点。同时，用size记录当前一叉堆中节点的个数。

用堆存储为：

对于一个破坏堆性质的结点可以使其上浮或下沉，因为最差也不过是上浮到顶或是下沉到底，所以只需要$O(lo{g}_{2}n)$的时间就可以完成。插入和删除都只需要上浮/下沉一个节点。

三、基本操作

元素上浮：

过程：

使要上浮的元素不断与父结点作比较，如果比父节点大或小就与之交换，直到不大于父结点或成为根结点为止。

代码;

大根堆：

void up(int i) {
    while (i > 1 && heap[i] > heap[i >> 1]) {
        swap(heap[i], heap[i >> 1]);
        i >>= 1;
    }
    return;
}

小根堆：

void up(int i) {
	while (i > 1 && heap[i] < heap[i >> 1]) {
		swap(heap[i], heap[i >> 1]);
		i >>= 1;
	}
	return;
}

元素下沉：

过程：

与上浮相类似，不断的将元素与较大的子结点比较，如果比它小或大，就与之交换，直到不小于任何子结点或成为叶子结点为止。

代码：

大根堆：

void down(int i) {
    while (i * 2 <= n) {
        int T = i * 2;
        if (T + 1 <= n & heap[T + 1] > heap[T]) {
            T++;
        }
        if (heap[i] < heap[T]) {
            swap(heap[i], heap[T]);
            i = T;
        } else break;
    }
}

小根堆：

void down(int i) {
	while (i * 2 <= n) {
		int T = i * 2;
		if (T + 1 <= n && heap[T + 1] < heap[T]) {
			T++;
		}
		if (heap[i] > heap[T]) {
			swap(heap[i], heap[T]);
			i = T;
		} else break;
	}
	return;
}

插入元素：

过程：

将元素插入到堆的尾部，将其上浮。

代码：

void insert(int i) {
	heap[++n] = i;
	up(n);
}

删除元素：

过程：

从堆中删除堆顶元素时，移除堆顶元素之后，用堆的最后一个节点填补取走的堆顶元素，并将堆的实际元素个数减1。再将最后一个元素下沉，使其满足堆性质。

代码：

void delet () {
	swap(heap[1], heap[n--]);
	down(1);
	return;
}

元素查询：

过程：

返回对顶元素即可；

代码：

int search() {
	return heap[1];
}

建立堆：

过程：

可以从一个数组$O(n)$地建立堆，只需复制过来然后从底部到顶部依次下沉即可。因为叶子节点不需要下沉，所以可以从n/2处开始遍历。

代码：

void build(int n) {
	memcpy(heap, a, sizeof(a));
	for (int i = n; i > 0; i--) {
		down(i);
	}
	return;
}

输出堆：

过程：

查询到堆顶元素输出后，将对顶元素删除，继续输出；

代码:

void print(int n) {
	for (int i = 1; i <= n; i++) {
		printf("%d ", search());
		delet();	
	}
}

四、例题

堆排序

题目描述

输入N个整数，进行二叉堆排序.输出结果.

输入格式

第1行：一个整数N(N≤100000)，表示个数。
第2行：N个空格分开的整数。

输出格式

第1行：N个空格分开的整数，以不降序排列。
注意，行末不得有多余的空格。

思路：

将读入的数组创立成小根堆，排序再输出即可；

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a[1000005], heap[1000005], ans[1000005];
void up(int i) {
	while (i > 1 && heap[i] < heap[i >> 1]) {
		swap(heap[i], heap[i >> 1]);
		i >>= 1;
	}
	return;
}
void down(int i) {
	while (i * 2 <= n) {
		int T = i * 2;
		if (T + 1 <= n && heap[T + 1] < heap[T]) {
			T++;
		}
		if (heap[i] > heap[T]) {
			swap(heap[i], heap[T]);
			i = T;
		} else break;
	}
	return;
}
void insert(int i) {
	heap[++n] = i;
	up(n);
}
void delet () {
	swap(heap[1], heap[n--]);
	down(1);
	return;
}
int search() {
	return heap[1];
}
void build(int n) {
	memcpy(heap, a, sizeof(a));
	for (int i = n; i > 0; i--) {
		down(i);
	}
	return;
}
void print(int n) {
	for (int i = 1; i <= n; i++) {
		printf("%d ", search());
		delet();	
	}
}
int main() {
	scanf("%d", &n);
	int m = n;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}
	build(m);
	print(m);
	return 0;
}