数据结构===堆

概要

堆，有趣的数据结构。

那么，如何实现一个堆呢？

堆

堆，有哪些重点：

1. 满足2条件
2. 大顶堆
3. 小顶堆

2条件

2条件：

1. 堆是一个完全二叉树
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 = capacityself.size = 0self.Heap = [0]*(self.capacity + 1)self.Heap[0] = -1 * sys.maxsizeself.FRONT = 1def parent(self, pos):return pos//2def leftChild(self, pos):return 2 * pos       def rightChild(self, pos):return (2 * pos) + 1def isLeaf(self, pos):if pos >= (self.size//2) and pos <= self.size:return Truereturn Falsedef 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 :returnself.size+= 1self.Heap[self.size] = elementcurrent = self.sizewhile 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-= 1self.heapifyDown(self.FRONT)return poppeddef isEmpty(self):return self.size == 0def isFull(self):return self.size == self.capacity

小结

关于堆，就这么多吧

堆的概念跟推理还是相对来说简单的。比红黑树简单点。其实都一样的，只要按照那些规则，一条一条对着去理解；应该还好。