- 浏览: 319395 次
- 性别:
- 来自: 西宁
文章分类
- 全部博客 (120)
- Java Thought (29)
- Java Pattern (4)
- Data Base (7)
- Algorithm Design (33)
- Linux (0)
- Mysql (2)
- Oracle (0)
- ConstructionDesign-架构 (5)
- Spring Platform (0)
- Tomcat (1)
- JavaScript (7)
- Web System (3)
- MS SQLServer (1)
- 软件哲学 (6)
- View (3)
- Java GUI (4)
- CSSDIV (7)
- CloudComputing (0)
- WebService (0)
- SystemOrProject (2)
- SOA (0)
- 互转共享 (3)
- 偶尔java习题 (0)
- Thinks with does (1)
最新评论
-
sassds:
佩服啊 高手
分享一款js特效 -
bhjackson:
学习啦,能否详细介绍下回溯的过程?O(∩_∩)O谢谢
分享回溯法- 找n个数中r个数的组合 -
zk7019311:
了解了解。。。。。
业务层代码复用的一点建议 -
lijie1819:
看到LZ的设计思想,感觉和抽象工厂模式有点相像。
业务层代码复用的一点建议 -
wjjcml1982:
酷毙了!楼主太强悍了!
分享一款js特效
说明: 对java数据结构中的堆的有关代码整理了一下,以备使用~~~
1. 堆结点:
2. 堆容器:
3. 堆应用测试
4. 堆排序测试:
1. 堆结点:
package boke.heap; /** * 堆结点 * * @since jdk1.5及其以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.24 * */ public class Node { private int iData; // 结点数据是整型 public Node(int key) { iData = key; } /** * setKey * * @param id */ public void setKey(int id) { iData = id; } /** * getKey * * @return */ public int getKey() { return iData; } }
2. 堆容器:
package boke.heap; /** * 堆 * * @since jdk1.5及其以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.24 * */ public class Heap { private Node[] heapArray; // 堆容器 private int maxSize; // 堆得最大大小 private int currentSize; // 堆得大小 /** * 构造 * * @param _maxSize */ public Heap(int _maxSize) { maxSize = _maxSize; currentSize = 0; heapArray = new Node[maxSize]; } /** * 堆是否为空 * * @return */ public boolean isEmpty() { return currentSize == 0; } /** * 在堆中插入新元素 * * @param key * @return */ public boolean insert(int key) { if (currentSize == maxSize) { return false; } Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true; } /** * 堆调整自下而上的调整 * * @param index */ public void trickleUp(int index) { int parent = (index - 1) / 2; Node bottom = heapArray[index]; while (index > 0 && heapArray[parent].getKey() < bottom.getKey()) { heapArray[index] = heapArray[parent]; // 双亲结点值大, 调整 index = parent; parent = (parent - 1) / 2; } heapArray[index] = bottom; // 回送 } /** * 删除堆中最大的值 * * @return */ public Node remove() { Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0); return root; } /** * 自上而下的调整 * * @param index */ public void trickleDown(int index) { int largeChild; Node top = heapArray[index]; // save root while (index < currentSize / 2) { // while node has at least one child int leftChild = 2 * index + 1; int rightChild = leftChild + 1; if (rightChild < currentSize && heapArray[leftChild].getKey() < heapArray[rightChild] .getKey()) { largeChild = rightChild; } else { largeChild = leftChild; } if (top.getKey() >= heapArray[largeChild].getKey()) { break; } heapArray[index] = heapArray[largeChild]; // shift child up index = largeChild; // go down } heapArray[index] = top; // root to index } /** * 改变堆中索引为index处的值 * * @param index * @param newValue * @return */ public boolean change(int index, int newValue) { if (index < 0 || index >= currentSize) { return false; } int oldValue = heapArray[index].getKey(); // remove old heapArray[index].setKey(newValue); // change to new if (oldValue < newValue) { // if raised this.trickleUp(index); // trickle it up } else { // if lowered this.trickleDown(index); // trickle it down } return true; } /** * 按某种格式输出堆 */ public void displayHeap() { System.out.print("heapArray: "); for (int i = 0; i < currentSize; i++) { if (heapArray[i] != null) { System.out.print(heapArray[i].getKey() + " "); } else { System.out.print("-- "); } } System.out.println(); int nBlanks = 32; // heap format int itemsPerRow = 1; int column = 0; int j = 0; // current item String dots = "..............................."; System.out.println(dots + dots); // dotted top line while (currentSize > 0) { // for each heap item if (column == 0) { // first item in row for (int k = 0; k < nBlanks; k++) { // preceding blanks System.out.print(" "); } } System.out.print(heapArray[j].getKey()); // display item if (++j == currentSize) { // done? break; } if (++column == itemsPerRow) { // end of row? nBlanks /= 2; // half the blanks itemsPerRow *= 2; // twice the items column = 0; // start over on System.out.println(); // next row } else { // next item on row for (int k = 0; k < nBlanks * 2 - 2; k++) { System.out.print(' '); // interim blanks } } } System.out.println("\n" + dots + dots); } /** * 输出堆数组 */ public void displayArray() { for (int j = 0; j < maxSize; j++) { System.out.print(heapArray[j].getKey() + " "); } System.out.println(""); } /** * 在堆中的索引index出设置新结点 * * @param index * @param newNode */ public void insertAt(int index, Node newNode) { heapArray[index] = newNode; } /** * 堆的大小增量 */ public void incrementSize() { currentSize++; } }
3. 堆应用测试
package boke.heap; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 堆应用测试 * * @since jdk1.5及其以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.24 * */ public class HeapApp { /** * @param args * @throws IOException */ public static void main(String[] args) throws IOException { int value, value2; Heap hp = new Heap(31); boolean success; hp.insert(70); hp.insert(40); hp.insert(50); hp.insert(20); hp.insert(60); hp.insert(100); hp.insert(80); hp.insert(30); hp.insert(10); hp.insert(90); while (true) { System.out.print("Enter first letter of "); System.out.print("show, insert, remove, change: "); int choice = getChar(); switch (choice) { case 's': hp.displayHeap(); break; case 'i': System.out.print("Enter value to insert: "); value = getInt(); success = hp.insert(value); if (!success) { System.out.println("Can't insert; heap is full"); } break; case 'r': if (!hp.isEmpty()) { hp.remove(); } else { System.out.println("Can't remove; heap is empty"); } break; case 'c': System.out.print("Enter current index of item: "); value = getInt(); System.out.print("Enter new key: "); value2 = getInt(); success = hp.change(value, value2); if (!success) { System.out.println("Invalid index"); } break; default: System.out.println("Invalid entry\n"); } } } /** * 获得控制台输入流 * * @return * @throws IOException */ public static String getString() throws IOException { return new BufferedReader(new InputStreamReader(System.in)).readLine(); } /** * 获得控制台输入字符 * * @return * @throws IOException */ public static char getChar() throws IOException { return getString().charAt(0); } /** * 获得控制台输入整型 * * @return * @throws NumberFormatException * @throws IOException */ public static int getInt() throws NumberFormatException, IOException { return Integer.parseInt(getString()); } }
4. 堆排序测试:
package boke.heap; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 堆排序测试 * * @since jdk1.5及其以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.24 * */ public class HeapSortApp { /** * @param args * @throws IOException * @throws NumberFormatException */ public static void main(String[] args) throws NumberFormatException, IOException { int size, j; System.out.print("Enter number of items: "); // 输入堆大小 size = getInt(); Heap hp = new Heap(size); for (j = 0; j < size; j++) { // 随机建立堆 int random = (int) (Math.random() * 100); Node newNode = new Node(random); hp.insertAt(j, newNode); hp.incrementSize(); } System.out.print("Random: "); hp.displayArray(); // 输出堆数组 for (j = size / 2 - 1; j >= 0; j--) { hp.trickleDown(j); } System.out.print("Heap: "); // 输出堆 hp.displayArray(); hp.displayHeap(); for (j = size - 1; j >= 0; j--) { Node largestNode = hp.remove(); hp.insertAt(j, largestNode); } System.out.print("Sorted: "); // 输出排序后的数组(升序) hp.displayArray(); } /** * 获得控制台输入流 * * @return * @throws IOException */ public static String getString() throws IOException { return new BufferedReader(new InputStreamReader(System.in)).readLine(); } /** * 获得控制台输入整型 * * @return * @throws NumberFormatException * @throws IOException */ public static int getInt() throws NumberFormatException, IOException { return Integer.parseInt(getString()); } }
发表评论
-
开散列的简单模拟(一)
2010-06-28 08:33 17831. 散列 散列有两种 ... -
递归和动态规划构造两个字符序列的最长公共字符子序列
2010-06-28 08:28 4464应je朋友要求,所以翻开以前的算法题目,整理了以下,给 ... -
最大公约数的应用 - 分享
2010-06-25 08:08 17891.先看一家大公司笔试题 数组中有n个数据,要将它们顺 ... -
信息数字化解逻辑题分享
2010-06-21 08:09 12241. 前提条件: 将逻辑题目中的信息用数字化描述。 ... -
递归算法分析-分享
2010-06-19 16:09 15301. 深入认识递归 (1) 递 ... -
非递归算法分析实例分享
2010-06-18 15:47 10161 仅仅依赖于问题规模的时间复杂度 (1) 例1: 交换i和 ... -
NP完全性问题
2010-06-18 14:02 6970在学习算法设计与分析时,经常会提到NP完全性问题,到底 ... -
算法分析精述分享
2010-06-18 12:03 8221. 算法分析的评价体系 评价算法的三条主要标准是: ... -
贪婪策略算法的总结分享
2010-06-11 08:30 59821. 贪婪算法描述 贪婪算法又叫登山法,它的根本思想是 ... -
带权有向图 - 边上权值非负情形的单源最短路径问题
2010-06-07 08:57 26351. 问题描述: 给定 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)四
2010-06-07 08:54 132421. 工作分配问题。 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)三
2010-06-07 08:53 105117. 字符统计问题。 编写一个算法,统计在一个输入 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)二
2010-06-07 08:47 13298. 数字迷问题。 A B C ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)一
2010-06-07 08:38 11341. 线程问题。 设计4个线程,其中两个线程每次对j增加 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)
2010-06-07 08:37 18391. 线程问题。 设计 ... -
Java快速排序算法整理(二)
2010-05-31 14:04 1009package boke.sort; /** * 快 ... -
Java快速排序算法整理(一)
2010-05-31 13:39 633package boke.sort; /** * 快 ... -
Java最小堆实现
2010-05-31 08:29 58061.堆结点 package boke.heap1; /* ... -
Java插入排序代码整理
2010-05-28 14:44 1213package boke.sort; /** * 插 ... -
Java选择排序代码整理
2010-05-28 14:37 1479package boke.sort; /** * 选 ...
相关推荐
十大排序算法十大排序算法源码,自己整理的,可以直接运行,Java版本
找工作期间整理的各种排序方式。有相关的Java代码和时间复杂度空间复杂度分析。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
堆(Heap-线程共享)-运行时数据区 ...................................................................................... 23 2.2.5. 方法区/永久代(线程共享) ..................................................
堆和栈的区别 20.ejb的分类及区别 21.你对现在软件业以及国内软件业的看法 22.谈谈java多线程 23.谈谈文件加密技术 24.软件开发生命周期 25.路由协议种类及特点 26.java的awt和swing组件的GUI设计的关键 27....
关于java程序员发展需要学习的路线整理集合 技术 应用技术 计算机基础知识 cpu mem disk net 线程,进程 第三方库 poi Jsoup zxing Gson 数据结构 树 栈 链表 队列 图 操作系统 linux 代码控制...
2.2.4. 堆(Heap-线程共享)-运行时数据区 ...................................................................................... 23 2.2.5. 方法区/永久代(线程共享) ............................................
堆排序 no NlogN 1 快速排序是最快的通用排序算法,它的内循环的指令很少,而且它还能利用缓存,因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN,这里的 c 比其他线性对数级别的排序算法都要小。使用三向...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
UP打算把八大排序算法中最难理解的几种整理一下,分别是归并排序、快排和堆排序。今天先介绍归并排序。 先说一下归并排序的图解 所谓的归并,是将两个或两个以上的有序文件合并成为一个新的有序文件,归并排序是把...
这其中每一个类文件都是一个可以单独运行查看结果的main方法类,相关的关键描述和想说的话都在代码的注释中。(欢迎一同补充和完善,2019年01月04日00:07:40置为public) 数组 线性数据结构及其对应的常见算法 ...
答:Class可以被实例化,属于引用类型,是分配在内存的堆上的,Struct属于值类型,是分配在内存的栈上的. [Page] 26.根据委托(delegate)的知识,请完成以下用户控件中代码片段的填写: namespace test { public ...
在开发代码的同时,如果你花费时间和精力来开发一个性能故障排错的方法。那么你就能避免这种情况——至少可以快速而有效地做出反应。《SQL Server 2008查询性能优化》指出的性能要点之一是数据库随着用户和数据的日...
在开发代码的同时,如果你花费时间和精力来开发一个性能故障排错的方法。那么你就能避免这种情况——至少可以快速而有效地做出反应。《SQL Server 2008查询性能优化》指出的性能要点之一是数据库随着用户和数据的日...
则需要进行全表扫描, 以便将数据按照所定义的语言排序进行整理。 值范围: BINARY 或有效的语言定义名。 默认值: 从 NLS_LANGUAGE 中获得 nls_territory: 说明: 为以下各项指定命名约定, 包括日期和星期的编号, ...