赞
踩
二叉堆是一种特殊的二叉树, 它总是保证一棵树的最小元素(最小堆)或者最大元素(最大堆)处于树根上, 常见的应用场景就是用于构建优先队列, 在jdk中Doug Lea所实现的ScheduledThreadPoolExecutor中就用到了最小堆;
计算机中树是一种数据结构(有向无环图), 因为它看起来像一颗倒挂的树, 所以被称为树。在计算机中对现实世界中的事物进行模拟与呈现, 树类型数据结构被应用在很多地方,
比如一个国家的行政区域划分
国家–>省—>市—>县—>乡—>镇—>村—>组
再如一个学校里学生的组织结构,
学校—>年级—>班级—>小组—>组成员
下面画图举例二叉堆的数据规则:
这里以最小堆为例讲解算法
假设这里要将一组无序整数构建到一棵最小堆里面去; {3, 5, 9, 1, 10, 8, 2, 12, 7, 4}
算法说明:首先最小堆的特性有, 规则一堆顶(二叉堆的根节点)为此堆中最小元素, 规则二每个节点的值大于其左右两节点的值, 针对同一组被构建的数据集合, 第一点规则下来, 确保跟节点的元素必定是固定的某一个值, 但是第二个规则下, 除了跟节点外的其他节点可能不同的构建算法最后得到的树是不一样的(具体哪个元素在哪个节点上); 规则二下, 我们发现树的左右子节点是无差别的;
将上面的二叉堆构建算法用编程语言实现时, 这里我们使用数组作为堆的底层数据结构, 转化与映射关系如下
/** * add one element to heap * * @param e element * @return add result */ private boolean addToHeap(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { if (this.size == heaps.length) { heaps = grow(); } siftUp(size++, e); return true; } finally { lock.unlock(); } } /** * Sifts element added at bottom up to its heap-ordered spot. * * @param k bottom index * @param item to bo moving */ private void siftUp(int k, E item) { while (k > 0) { int parent = (k - 1) >>> 1; E e = (E) heaps[parent]; if (compareTo(item, e) >= 0) { break; } heaps[k] = e; k = parent; } heaps[k] = item; }
/** * remove element from heap * * @param x to be remove * @return remove result */ private boolean remove(E x) { final ReentrantLock lock = this.lock; lock.lock(); try { int i = indexOf(x); if (i < 0) { return false; } int s = --size; E replacement = (E) heaps[s]; heaps[s] = null; if (s != i) { siftDown(i, replacement); if (heaps[i] == replacement) { siftUp(i, replacement); } } return true; } finally { lock.unlock(); } } /** * Sifts element added at top down to its heap-ordered spot. Call only when holding lock. * * @param k start index for siftDown * @param item the item to be sift */ private void siftDown(int k, E item) { int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; E c = (E) heaps[child]; int right = child + 1; if (right < size && compareTo(c, (E) heaps[right]) > 0) { c = (E) heaps[child = right]; } if (compareTo(item, c) <= 0) { break; } heaps[k] = c; k = child; } heaps[k] = item; }
/** * sort the heap by HeapSort * * @return the top of element */ public List<E> sort() { return size > 0 ? sort(false) : null; } /** * sort the heap by HeapSort * * @param newHeap if use newHeap for use less time * @return sort arrays */ private List<E> sort(boolean newHeap) { final ReentrantLock lock = this.lock; lock.lock(); try { if (size <= 0) { return null; } Object[] newHeaps = newHeap ? Arrays.copyOf(heaps, size) : heaps; int heapSize = this.size; for (int i = 0; size-- > 0; i++) { Object top = heaps[0]; heaps[0] = heaps[size]; siftDown(0, (E) heaps[0]); if (newHeap) { newHeaps[i] = top; } else { newHeaps[size] = top; } } this.size = heapSize; if (!newHeap) { // not use new-heap in sort, so we need to do a reverse for (int i = 0, j = this.size >>> 1, k = this.size - 1; i < j; i++) { Object temporary = newHeaps[i]; newHeaps[i] = newHeaps[k - i]; newHeaps[k - i] = temporary; } } return Arrays.asList(newHeaps).stream().map(item -> (E) item).collect(Collectors.toList()); } finally { lock.unlock(); } }
@Test(testName = "测试使用二叉堆示例") public void testAesUtilEncryptAndDecryptToStr() { // 构建一个二叉堆, 内部存放int数据 Integer[] data = {3, 5, 9, 1, 10, 8, 2, 12, 7, 4}; System.out.println("============== 最小堆示例 =============="); BinaryHeap<Integer> heap = new BinaryHeap(); for (int i = 0; i < data.length; i++) { heap.add(data[i]); } System.out.println(heap); System.out.println("============== 最小堆构建好了, 现在依次弹出堆顶元素, 再看堆中数据排布 =============="); while (heap.size() > 0) { heap.popTop(); System.out.println(heap); } System.out.println("============== 最大堆示例 =============="); heap = new BinaryHeap(true); for (int i = 0; i < data.length; i++) { heap.add(data[i]); } System.out.println(heap); System.out.println("============== 最大堆构建好了, 现在依次弹出堆顶元素, 再看堆中数据排布 =============="); while (heap.size() > 0) { heap.popTop(); System.out.println(heap); } System.out.println("============== 堆排序示例 =============="); heap = new BinaryHeap(); for (int i = 0; i < data.length; i++) { heap.add(data[i]); } List<Integer> sort = heap.sort(); System.out.println(sort); }
============== 最小堆示例 ============== BinaryHeap{heaps=[1, 3, 2, 5, 4, 9, 8, 12, 7, 10]} ============== 最小堆构建好了, 现在依次弹出堆顶元素, 再看堆中数据排布 ============== BinaryHeap{heaps=[2, 3, 8, 5, 4, 9, 10, 12, 7]} BinaryHeap{heaps=[3, 4, 8, 5, 7, 9, 10, 12]} BinaryHeap{heaps=[4, 5, 8, 12, 7, 9, 10]} BinaryHeap{heaps=[5, 7, 8, 12, 10, 9]} BinaryHeap{heaps=[7, 9, 8, 12, 10]} BinaryHeap{heaps=[8, 9, 10, 12]} BinaryHeap{heaps=[9, 12, 10]} BinaryHeap{heaps=[10, 12]} BinaryHeap{heaps=[12]} BinaryHeap{heaps=[]} ============== 最大堆示例 ============== BinaryHeap{heaps=[12, 10, 8, 9, 4, 5, 2, 1, 7, 3]} ============== 最大堆构建好了, 现在依次弹出堆顶元素, 再看堆中数据排布 ============== BinaryHeap{heaps=[10, 9, 8, 7, 4, 5, 2, 1, 3]} BinaryHeap{heaps=[9, 7, 8, 3, 4, 5, 2, 1]} BinaryHeap{heaps=[8, 7, 5, 3, 4, 1, 2]} BinaryHeap{heaps=[7, 4, 5, 3, 2, 1]} BinaryHeap{heaps=[5, 4, 1, 3, 2]} BinaryHeap{heaps=[4, 3, 1, 2]} BinaryHeap{heaps=[3, 2, 1]} BinaryHeap{heaps=[2, 1]} BinaryHeap{heaps=[1]} BinaryHeap{heaps=[]} ============== 堆排序示例 ============== [1, 2, 3, 4, 5, 7, 8, 9, 10, 12]
堆排序可以, 我们可以把堆顶元素挪到堆的最后一个元素位置, 然后将前面n-1个元素重新构建堆, 如此反复, 就能形成一个有序的堆;
在jdk中有一个定时调度线程池, 它的内部便是采用一个最小堆保存需要被调度执行的任务, 堆顶便是未来最先需要被调度的任务, 插入和弹出操作都需要维护堆的有效性, 都需要加同步锁,;
注:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。