package com.pskfire.sort;
// heapSort.java
// demonstrates heap sort
// to run this program: C>java HeapSortApp
import java.io.*;
////////////////////////////////////////////////////////////////
class Node {
private int iData; // data item (key)
// -------------------------------------------------------------
public Node(int key) // constructor
{
iData = key;
}
// -------------------------------------------------------------
public int getKey() {
return iData;
}
// -------------------------------------------------------------
} // end class Node
// //////////////////////////////////////////////////////////////
class Heap {
private Node[] heapArray;
private int maxSize; // size of array
private int currentSize; // number of items in array
// -------------------------------------------------------------
public Heap(int mx) // constructor
{
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize];
}
// -------------------------------------------------------------
public Node remove() // delete item with max key
{ // (assumes non-empty list)
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
} // end remove()
// -------------------------------------------------------------
public void trickleDown(int index) {
int largerChild;
Node top = heapArray[index]; // save root
while (index < currentSize / 2) // not on bottom row
{
int leftChild = 2 * index + 1;
int rightChild = leftChild + 1;
// find larger child
if (rightChild < currentSize && // right ch exists?
heapArray[leftChild].getKey() < heapArray[rightChild]
.getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if (top.getKey() >= heapArray[largerChild].getKey())
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // go down
} // end while
heapArray[index] = top; // root to index
} // end trickleDown()
// -------------------------------------------------------------
public void displayHeap() {
int nBlanks = 32;
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(' ');
// display item
System.out.print(heapArray[j].getKey());
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(); // new row
} else
// next item on row
for (int k = 0; k < nBlanks * 2 - 2; k++)
System.out.print(' '); // interim blanks
} // end for
System.out.println("\n" + dots + dots); // dotted bottom line
} // end displayHeap()
// -------------------------------------------------------------
public void displayArray() {
for (int j = 0; j < maxSize; j++)
System.out.print(heapArray[j].getKey() + " ");
System.out.println("");
}
// -------------------------------------------------------------
public void insertAt(int index, Node newNode) {
heapArray[index] = newNode;
}
// -------------------------------------------------------------
public void incrementSize() {
currentSize++;
}
// -------------------------------------------------------------
} // end class Heap
// //////////////////////////////////////////////////////////////
class HeapSortApp {
public static void main(String[] args) throws IOException {
int size, j;
System.out.print("Enter number of items: ");
size = getInt();
Heap theHeap = new Heap(size);
for (j = 0; j < size; j++) // fill array with
{ // random nodes
int random = (int) (java.lang.Math.random() * 100);
Node newNode = new Node(random);
theHeap.insertAt(j, newNode);
theHeap.incrementSize();
}
System.out.print("Random: ");
theHeap.displayArray(); // display random array
for (j = size / 2 - 1; j >= 0; j--)
// make random array into heap
theHeap.trickleDown(j);
System.out.print("Heap: ");
theHeap.displayArray(); // dislay heap array
theHeap.displayHeap(); // display heap
for (j = size - 1; j >= 0; j--) // remove from heap and
{ // store at array end
Node biggestNode = theHeap.remove();
theHeap.insertAt(j, biggestNode);
}
System.out.print("Sorted: ");
theHeap.displayArray(); // display sorted array
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class HeapSortApp
// //////////////////////////////////////////////////////////////
分享到:
相关推荐
在准备Java面试的过程中,数据结构是必不可少的知识领域。数据结构是计算机存储、组织数据的方式,它直接影响到程序的效率和性能。本资料包主要聚焦于Java实现的数据结构,旨在帮助面试者深入理解并掌握这些核心概念...
数据结构是计算机科学中的核心概念,它涉及到如何高效地存储和操作数据。堆排序是一种基于比较的排序算法,它的效率高且实现简单。在本文中,我们将深入探讨堆排序的原理,以及如何在实际编程中实现它。 首先,我们...
数据结构是计算机科学中的核心课程,它探讨了如何有效地组织和管理数据,以便于高效地执行各种操作。这篇文档是北京大学2000年的数据结构考研试题,涵盖了多个关键概念和算法。 首先,简述的概念包括哈希树、完全...
堆排序是一种高效的排序算法,基于完全二叉树的特性实现。在这个"heapsort.rar"压缩包中,包含了一个名为"heapsort.cpp"的源代码文件,这...同时,堆排序的思想也被广泛应用于其他数据结构和算法设计中,如优先队列等。
Java 数据结构之堆排序(HeapSort)详解及实例 堆排序是一种常用的排序算法,它将数组分为大根堆和小根堆,并利用堆的性质对数组进行排序。在 Java 中,堆排序可以通过构建最大堆、选择堆顶元素、交换堆顶元素与第 ...
《浙江大学高级数据结构课件》是一份非常宝贵的教育资源,它涵盖了数据结构这一计算机科学核心领域的深入知识。数据结构是编程和算法设计的基础,对于任何希望在IT领域有所建树的人来说,都是不可或缺的一部分。这份...
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
堆排序的实现,支持文件导入和手动写入数字进行排序,简单易懂,欢迎给位下载学习使用
数据结构课程设计五——排序算法综合分析 该资源是一个数据结构课程设计的五个部分,主要讲解排序算法的综合分析。该资源涵盖了多种排序算法,包括直接插入排序、希尔排序、快速排序、冒泡排序、堆排序和归并法排序...
数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法...
全集内容结构如下: ├─图 │ ├─关键路径(有向无环图及其应用2) │ │ 1.txt │ │ ALGraph.cpp │ │ ALGraph.h │ │ CriticalPath.cpp │ │ CriticalPath.h │ │ InfoType.cpp │ │ InfoType.h │ │ ...
数据结构是计算机科学中的核心课程之一,它研究如何在计算机中高效地组织和管理数据,以便于进行快速的存取和处理。清华大学的这本数据结构讲义PPT,涵盖了该领域的基本概念、主要类型以及实际应用,对于学习者深入...
heapsort-example:Cascadia College BIT 265-数据结构和算法-Heapsort演示代码
自己写的一些简单算法和数据结构的代码 快排 堆排 归并 二分查找 单链表
《学生成绩管理系统-数据结构》 在信息技术领域,数据结构是编程中至关重要的一部分,它涉及到如何有效地存储和管理数据,以便于高效地访问和处理。在这个“学生成绩管理系统”中,数据结构起着核心作用,它为学生...
数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行...
堆排序(Heapsort)是指利用堆这种数据结构(后面的【图解数据结构】内容会讲解分析)所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的...
各种基本数据结构在不同场景下的时间复杂度 在计算机科学中,时间复杂度是指算法执行所需的时间量,它是衡量算法性能的一个重要指标。不同的数据结构在不同的场景下具有不同的时间复杂度,本资源将详细介绍各种基本...
数据结构是计算机科学中的核心概念,它涉及到如何在内存中有效地组织和管理数据,以便进行高效的操作。在C语言中实现数据结构算法,可以更好地理解底层机制,提高程序的性能。"数据结构算法与应用-C语言描述(下)...