数据结构——堆

数据结构——堆

​

一。什么是堆

堆是一棵完全二叉树（高度为logn），特点是父节点的值大于两个子节点的值（当然也可以建立小于关系的堆），通常应用于堆排序、优先队列等

二。堆的基本元素

a[1~n]：用于存储数据；

par(x)：x的父节点，即floor（x/2）；

right(x)：x的左孩子，即x*2;

left(x)：x的右孩子，即x*2+1;

heapsize(a)：堆a当前的元素个数。

三。堆的基本操作

1.堆的性质保持：

加定以left（t）和right（t）为根节点的子树已经是堆，现在要调整以t为根节点的树，使之成为堆

void heapify(int *a, int i) { int L = i<<1, R = i<<1|1, largest; if (L <= heapsize) largest = a[L] > a[i] ? L, i; if (R <= heapsize) largest = a[R] > a[largest] ? R : largest; if (largest != i) { swap(a[i], a[largest]); heapify(a, largest); }}

2.建堆

void buildheap(int a) { for (int i = heapsize / 2; i >= 1; i--) heapify(a, i);}

四。堆的应用

1.堆排序

void heapsort(int *a) { buildheap(a); for (int i = heapsize; i > 1; i--) { swap(a[1], a[i]); heapsize--; heapify(a, 1); }}

2.优先队列

void getmax(int *a) { int max = a[1]; a[1] = a[n]; heapsize--; heapify(a, 1); return max;}void Insert(int *a, int i) { int n = ++heapsize, par = i / 2; a[n] = -INF; while (n > 1 && a[par] < i) { a[n] = a[par]; n = par[n]; } a[n] = i;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。