AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

数据结构之堆

2017-05-17 1385
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
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

////////////////////////////////////////////////////////////////
文章转自庄周梦蝶  ，原文发布时间5.17
文章标签：
Java
Go
boxti
目录
相关文章
ephemerals__
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
1028 16
2的n次方_
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
630 5
【数据结构】优先级队列（堆）从实现到应用详解
神明木佑
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
667 1
椰椰椰耶
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
椰椰椰耶
1045 0
平凡程序猿~
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
平凡程序猿~
920 1
平凡程序猿~
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
407 1
是店小二呀
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
是店小二呀
412 1
爱发白日梦的后端
|
搜索推荐 算法 Go
深入探索堆：Go语言中的高效数据结构
深入探索堆：Go语言中的高效数据结构
爱发白日梦的后端
373 7
大柏怎么被偷了
|
存储 算法
【数据结构】堆
【数据结构】堆
大柏怎么被偷了
277 3
chian-ocean
【数据结构】二叉树顺序实现（大堆）--＞赋源码
【数据结构】二叉树顺序实现（大堆）--＞赋源码
chian-ocean
262 4

热门文章

最新文章

  • 1
    数据结构学习笔记——图的遍历算法（深度优先搜索和广度优先搜索）
  • 2
    【数据结构入门】-堆的实现以及堆排序（2）
  • 3
    [数据结构] 数组与链表的优缺点和区别
  • 4
    数据结构六：图（DataWhale系列）
  • 5
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
  • 6
    【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
  • 7
    数据结构（严蔚敏版）第三章——栈和队列（二）【栈的表示和操作的实现】
  • 8
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
  • 9
    数据结构（1）：使用面向对象模拟数组
  • 10
    Python教程：一文了解10种数据结构在Python中的实现方法
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    900
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    810
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    927
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    1164
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    995
  • 6
    Redis基础命令与数据结构概览
    474
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    671
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    1020
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    1004
  • 10
    Redis核心数据结构与分布式锁实现详解
    1425

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！