概要
堆，有趣的数据结构。
那么，如何实现一个堆呢？
堆
堆，有哪些重点：
- 满足2条件
- 大顶堆
- 小顶堆
2条件
2条件：
- 堆是一个完全二叉树
- 堆中的每个节点的值都必须大于等于或小于等于其树中每个节点的值
堆要满足这2个条件，重点。即使后边插入数据，或者删除数据之后，还是要满足这2个条件来做调整。
大顶堆
特点：
每个节点的值都大于等于子树中每个节点值的堆。
小顶堆
特点：
每个节点的值都小于等于子树中每个节点值的堆。
堆的实现
实现一个堆，重要的操作：插入元素和删除堆顶元素
插入元素
堆化：顺着节点所在的路径，向上或者向下，对比，然后交换。
来看下插入的代码：
public class Heap { private int[] a; // 数组，从下标1开始存储数据 private int n; // 堆可以存储的最大数据个数 private int count; // 堆中已经存储的数据个数 public Heap(int capacity) { a = new int[capacity + 1]; n = capacity; count = 0; } public void insert(int data) { if (count >= n) return; // 堆满了 ++count; a[count] = data; int i = count; while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化 swap(a, i, i/2); i = i/2; } } }
删除堆顶元素
由大顶堆和小顶堆的定义可知，堆顶元素要么最大，要么最小；
public void removeMax() { if (count == 0) return -1; // 堆中没有数据 a[1] = a[count]; --count; heapify(a, count, 1); } private void heapify(int[] a, int n, int i) { // 自上往下堆化 while (true) { int maxPos = i; if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2; if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1; if (maxPos == i) break; swap(a, i, maxPos); i = maxPos; } }
堆代码
来看个完整的代码吧，这里给python的。如下：
import sys class BinaryHeap: def __init__(self, capacity): self.capacity = capacity self.size = 0 self.Heap = [0]*(self.capacity + 1) self.Heap[0] = -1 * sys.maxsize self.FRONT = 1 def parent(self, pos): return pos//2 def leftChild(self, pos): return 2 * pos def rightChild(self, pos): return (2 * pos) + 1 def isLeaf(self, pos): if pos >= (self.size//2) and pos <= self.size: return True return False def swap(self, fpos, spos): self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos] def heapifyDown(self, pos): if not self.isLeaf(pos): if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or self.Heap[pos] > self.Heap[self.rightChild(pos)]): if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]: self.swap(pos, self.leftChild(pos)) self.heapifyDown(self.leftChild(pos)) else: self.swap(pos, self.rightChild(pos)) self.heapifyDown(self.rightChild(pos)) def insert(self, element): if self.size >= self.capacity : return self.size+= 1 self.Heap[self.size] = element current = self.size while self.Heap[current] < self.Heap[self.parent(current)]: self.swap(current, self.parent(current)) current = self.parent(current) def minHeap(self): for pos in range(self.size//2, 0, -1): self.heapifyDown(pos) def delete(self): popped = self.Heap[self.FRONT] self.Heap[self.FRONT] = self.Heap[self.size] self.size-= 1 self.heapifyDown(self.FRONT) return popped def isEmpty(self): return self.size == 0 def isFull(self): return self.size == self.capacity
小结
关于堆，就这么多吧
堆的概念跟推理还是相对来说简单的。比红黑树简单点。其实都一样的，只要按照那些规则，一条一条对着去理解；应该还好。
