public class Heap { public static void siftUp(int[] array, int i) { if (array == null || array.length <= 1 || i < 0 || i > array.length) { return; } while (true) { if (array[(i - 1) / 2] < array[i]) { swap(array, i, (i - 1) / 2); } else { break; } i = (i - 1) / 2; } } public static void siftDown(int[] array, int i) { if (array == null || array.length <= 1 || i < 0 || i > array.length) { return; } while (true) { int left = 2 * i + 1; int right = 2 * i + 2; if (right >= array.length) { if (left < array.length && array[i] < array[left]) { swap(array, i, left); } break; } int target = array[left] > array[right] ? left : right; if (array[target] > array[i]) { swap(array, i, target); } i = target; } } public static void siftDown(int[] array, int end, int i) { if (array == null || i < 0 || i > end) { return; } while (true) { int left = 2 * i + 1; int right = 2 * i + 2; if (right > end) { if (left < end && array[i] < array[left]) { swap(array, i, left); } break; } int target = array[left] > array[right] ? left : right; if (array[target] > array[i]) { swap(array, i, target); } i = target; } } /** * put the element to insert to the last * * @param array * @param i */ public static void insert(int[] array) { siftUp(array, array.length - 1); } public static void delete(int[] array, int i) { if (array == null || array.length <= 1 || i < 0 || i > array.length) { return; } int tmp = array[i]; array[i] = -1; if (i == array.length) { return; } swap(array, i, array.length - 1); if (array[i] > tmp) siftUp(array, i); else siftDown(array, i); } public static int deleteMax(int[] array) { int result = array[0]; delete(array, 0); return result; } public static void makeHeap(int[] array) { if (array == null || array.length <= 1) { return; } for (int i = (array.length - 2) / 2; i >= 0; i--) { siftDown(array, i); } } public static void heapSort(int[] array) { if (array == null || array.length <= 1) { return; } makeHeap(array); for (int i = array.length - 1; i >= 0; i--) { swap(array, 0, i); siftDown(array, i - 1, 0); } } public static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void main(String[] args) { int[] array = { 20, 17, 9, 10, 31, 4, 5, 3, 7, 5 }; Heap.siftUp(array, 4); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); int[] array2 = { 2, 17, 9, 10, 11, 4, 5, 3, 7, 5 }; Heap.siftDown(array2, 0); for (int i = 0; i < array2.length; i++) { System.out.print(array2[i] + " "); } System.out.println(); int[] array3 = { 20, 17, 9, 10, 11, 4, 5, 3, 7, 5, 30 }; Heap.insert(array3); for (int i = 0; i < array3.length; i++) { System.out.print(array3[i] + " "); } System.out.println(); int[] array4 = { 20, 17, 9, 10, 11, 4, 5, 3, 7, 5 }; Heap.delete(array4, 5); for (int i = 0; i < array4.length; i++) { System.out.print(array4[i] + " "); } System.out.println(); int[] array5 = { 5, 6, 3, 7, 8, 1, 10 }; Heap.heapSort(array5); for (int i = 0; i < array5.length; i++) { System.out.print(array5[i] + " "); } System.out.println(); } }
相关推荐
c语言实现 小根堆heap,每次pop的时候都是最小值。整个值以数组形式储存!
基于python的数据结构代码实现-堆Heap
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
15年7月最新版的工具Heap Analzer V4。 分析java内存堆快照的利器,拥有直觉性的判断溢出对象是什么,一目了然。支持上下左右键,免去鼠标点击的痛苦。 对象显示也比较详细,数量,大小都包含,支持对象树的复制。
java中堆(heap)和堆栈(stack)有什么区别
用C++和模板实现最大堆,可用于简单排序操作
eager binomial heaps python实现。使用双向链表,make_heap, insert, merge, find_min, extractMin.
通过heapdump工具分析服务器堆分配问题
在clion中对fibonacci heap的完全实现,亲测有效。
堆溢出攻击教程(heap overflow attack)
最近在学习STL的源代码,看到这么多优秀的代码,心里痒痒的,于是自己实现了一遍,当然,有自己的特色,都是模块函数,稍稍用了一些traits特性。相互学习,呵呵
JVM堆分析,Java VM堆分析(节选)。 JProbe 是目前最好的Java性能优化工具之一,在全球有最多的用户。 本文档不但介绍了JProbe的在解决内存问题方面的功能和使用,同时还介绍了必要的Java内存管理的背景知识,深入...
2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。3、全局区(静态区)(static)—全局变量和静态变量的存储是放在一块...
c++ code for MaxHeap Sort
Visual C++ 小内存堆(Small Block Heap)问题
ibm-java-堆内存分析工具-heapanalyzer
Heap堆解题套路【LeetCode刷题套路教程6】
David Litchfield课件 源码c语言
void heap_sort(int A[],int length) { BUILD_MAX_HEAP(A,length); int i,middle; for(i=length-1;i>0;i--) { middle=A[0]; A[0]=A[i]; A[i]=middle; heap_size--; MAX_HEAPIFY(A,0); } }
二项堆(Binomial Heap)的c语言完全实现,包括添加,删除,和找到最小值,删除最小值