1。概念：堆是一种特殊的二叉树，具备以下两种性质
1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值
2）树是完全平衡的，并且最后一层的树叶都在最左边
这样就定义了一个最大堆。
2。堆可以用一个数组表示，有如下性质：
heap[i]>=heap[2*i+1] 其中0<=i<=(n-1)/2
heap[i]>=heap[2*i+2] 其中0<=i<=(n-2)/2
3。用数组实现堆，
1）插入操作
自顶向下，伪代码：
heapEnqueue(el)
将el放在堆尾
while el不在根节点并且el>parent(el)
交换el及其父节点
自底向上，伪代码：
FloydAlgrithm(data[])
for i=最后一个非叶节点的下标,i>=0;i--
调用moveDown(data,i,n-1)恢复以data[i]为根的树的堆性质
2)moveDown的方法实现，此方法是堆排序的关键，也是删除操作的关键。删除操作，将根节点删除，并把最末的树叶换到根节点，通过moveDown方法找到正确的位置，恢复堆性质。
4。堆的一个实现：
// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;
////////////////////////////////////////////////////////////////
class Node
{
private int iData; // data item (key)
// -------------------------------------------------------------
public Node(int key) // constructor
{ iData = key; }
// -------------------------------------------------------------
public int getKey()
{ return iData; }
// -------------------------------------------------------------
public void setKey(int id)
{ iData = id; }
// -------------------------------------------------------------
} // end class Node
////////////////////////////////////////////////////////////////
class Heap
{
private Node[] heapArray;
private int maxSize; // size of array
private int currentSize; // number of nodes in array
// -------------------------------------------------------------
public Heap(int mx) // constructor
{
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize]; // create array
}
// -------------------------------------------------------------
public boolean isEmpty()
{ return currentSize==0; }
// -------------------------------------------------------------
public boolean insert(int key)
{
if(currentSize==maxSize)
return false;
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
trickleUp(currentSize++);
return true;
} // end insert()
// -------------------------------------------------------------
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]; // move it down
index = parent;
parent = (parent-1) / 2;
} // end while
heapArray[index] = bottom;
} // end trickleUp()
// -------------------------------------------------------------
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) // while node has at
{ // least one child,
int leftChild = 2*index+1;
int rightChild = leftChild+1;
// find larger child
if(rightChild < currentSize && // (rightChild 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 boolean change(int index, int newValue)
{
if(index<0 || index>=currentSize)
return false;
int oldValue = heapArray[index].getKey(); // remember old
heapArray[index].setKey(newValue); // change to new
if(oldValue < newValue) // if raised,
trickleUp(index); // trickle it up
else // if lowered,
trickleDown(index); // trickle it down
return true;
} // end change()
// -------------------------------------------------------------
public void displayHeap()
{
System.out.print("heapArray: "); // array format
for(int m=0; m<currentSize; m++)
if(heapArray[m] != null)
System.out.print( heapArray[m].getKey() + " ");
else
System.out.print( "-- ");
System.out.println();
// heap format
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()
// -------------------------------------------------------------
} // end class Heap
////////////////////////////////////////////////////////////////
class HeapApp
{
public static void main(String[] args) throws IOException
{
int value, value2;
Heap theHeap = new Heap(31); // make a Heap; max size 31
boolean success;
theHeap.insert(70); // insert 10 items
theHeap.insert(40);
theHeap.insert(50);
theHeap.insert(20);
theHeap.insert(60);
theHeap.insert(100);
theHeap.insert(80);
theHeap.insert(30);
theHeap.insert(10);
theHeap.insert(90);
while(true) // until [Ctrl]-[C]
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, remove, change: ");
int choice = getChar();
switch(choice)
{
case 's': // show
theHeap.displayHeap();
break;
case 'i': // insert
System.out.print("Enter value to insert: ");
value = getInt();
success = theHeap.insert(value);
if( !success )
System.out.println("Can't insert; heap full");
break;
case 'r': // remove
if( !theHeap.isEmpty() )
theHeap.remove();
else
System.out.println("Can't remove; heap empty");
break;
case 'c': // change
System.out.print("Enter current index of item: ");
value = getInt();
System.out.print("Enter new key: ");
value2 = getInt();
success = theHeap.change(value, value2);
if( !success )
System.out.println("Invalid index");
break;
default:
System.out.println("Invalid entry/n");
} // end switch
} // end while
} // 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 char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//-------------------------------------------------------------
} // end class HeapApp
////////////////////////////////////////////////////////////////
分享到：
相关推荐
【数据结构之堆1】是关于数据结构中堆的详细解析，主要涵盖了堆的概念、分类、常见操作以及在LeetCode等刷题平台上的应用。堆作为一种特殊的完全二叉树，通常用于实现优先队列，以高效地进行最大值或最小值的查找、...
堆是一种特殊的树形数据结构，每个节点都有一个值，并且满足以下性质：对于任何非叶节点，其值都大于或等于（最大堆）或小于或等于（最小堆）它的子节点的值。在最大堆中，根节点是所有节点中最大的；在最小堆中，根...
堆是一种特殊的数据结构，通常被用作优先队列的底层实现。在本主题中，我们将深入探讨堆的实现，特别是标准大学课程中教授的方法。 堆通常是一个完全二叉树，分为两种类型：最大堆和最小堆。在最大堆中，每个节点的...
数据结构习题堆排序程序，将每行代码前的注释去掉即可运行
按照算法导论上的伪代码写出的堆数据结构，实现的是最大堆的堆排序
堆结构是数据结构的重要组成部分，它是一种特殊的完全二叉树，具有结构性和有序性两个主要特性。结构性是指用数组表示的完全二叉树，即对于数组中的任意位置i（从1开始计数），其左子节点的位置是2i，右子节点的位置...
堆是一种特殊的数据结构，它常被用于实现优先队列。在优先队列中，待删除的元素是优先级最高（或最低）的那个。堆结构允许在任何时间插入任意优先级的元素到队列中去。在计算机科学中，堆被定义为一棵每一个节点的...
数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序 数据结构——堆排序
堆，作为一种特殊的数据结构，是实现优先队列的典型数据结构。它通常表现为一棵完全二叉树，且具有以下特性：对于大顶堆，每个父节点的值都大于或等于其子节点的值；对于小顶堆，父节点的值小于或等于子节点的值。...
8. **堆**：堆是一种特殊的树形数据结构，满足堆属性（最大堆或最小堆），常用于实现优先队列。堆排序是一种基于堆的高效排序算法。 9. **文件系统**：在计算机系统中，文件系统使用数据结构来管理磁盘上的文件和...
数据结构堆排序的java算法实现，里面用java语言实现了堆排序的算法实现，有输入和输出结果
本课件讲述堆排序的中建堆和排序的过程，并有详细的过程描述，对于建堆的过程有详细和动画介绍，通俗易懂，有助于学习和帮助
数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和存储数据，以便于进行各种操作。上海交通大学的数据结构课件是学习这一主题的重要资源，它涵盖了广泛的知识点，帮助学生深入理解数据结构...
高级数据结构——堆在解题中的应用这篇文档，主要围绕堆这种数据结构的定义、性质、操作以及应用场景进行了详细的讨论。文章首先定义了堆的概念，指出堆是一棵完全二叉树，它满足特定的父子节点值的关系：在最大堆中...
数据结构实验，顺序表单链表的基本操作，堆排序等到等
8. **堆**：堆是一种特殊的树形数据结构，满足最大堆或最小堆的性质，常用于优先队列的实现。C语言中，可以使用数组模拟堆。 9. **排序算法**：包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等，...
数据结构最大堆的实现，通过改编最小堆的模板，实现最大堆操作。
8. **堆**：堆是一种特殊的树形数据结构，满足堆性质，即父节点的值总是大于或等于（最小堆）或小于或等于（最大堆）其子节点的值。堆常用于优先队列和某些排序算法，如堆排序。 9. **排序算法**：在C语言中，学习...
本文实例为大家分享了C语言堆排序源代码，供大家参考，具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科： 用一句概括，堆排序就是一种改进的选择排序，改进的地方在于，每次做选择的时候，不单单把最大...
8. **堆数据结构**：堆是一种特殊的树形数据结构，满足堆性质（最大堆或最小堆）。堆通常用于实现优先队列，实验中会涉及到堆的构建、插入、删除操作。 9. **文件与外部存储**：当数据量过大无法全部存放在内存时，...