java数据结构----堆

ipqtjmqj

2018-11-16

1.堆：堆是一种树，由它实现的优先级队列的插入和删除的时间复杂度都是O(logn)，用堆实现的优先级队列虽然和数组实现相比较删除慢了些，但插入的时间快的多了。当速度很重要且有很多插入操作时，可以选择堆来实现优先级队列。

优先队列可以用堆实现也可用数组实现

一般用来存树（包括堆）的数组都是树的层序遍历的结果

堆的顺序是弱序的只是保证垂直路劲上有顺序（移除添加之后新的还是有顺序，最顶端的是最值，当把全部出来的拼在一起就有序了），水平顺序上无序，不像平衡二叉树是严格的顺序，堆只能用来弹出最大、最小值

2.java的堆和数据结构堆：java的堆是程序员用new能得到的计算机内存的可用部分。而数据结构的堆是一种特殊的二叉树。
3.堆是具有如下特点的二叉树：
　　3.1.它是完全二叉树，也就是说除了树的最后一层节点不需要是满的，其他的每一层从左到右都必须是满的。

　　3.1.1.完全二叉树图解： java数据结构----堆

3.2.它常常用数组实现。

　　3.2.1.数组和堆的对应关系示意图： java数据结构----堆

3.3.堆中每一个节点都满足堆的条件，也就是说每一个关键字的值都大于或等于这个节点的子节点的关键字值。
　　堆是完全二叉树的事实说明了表示堆的数组中没有空项，即从0-->n-1的每个数据单元都有数据项。
4.堆在存储器中的表示是数组，堆只是一个概念上的表示。

5.堆的弱序：堆和二叉搜索树相比是弱序的，在二叉搜索树中，当前节点的值总是比左子节点的值大，却比它的右子节点的值小，因此按序遍历相对容易。而堆的组织规则弱，它只要求从根到叶子节点的每一条路径，节点都是按降序排列的。同一节点的左右子节点都没有规律。因此，堆不支持按序遍历，也不能在堆上便利的查找指定关键字，因为在查找的过程中，没有足够的信息决定选择通过节点的两个那一个走向下一层。它也不能在少于O(logn)的时间内删除一个指定的节点，因为没有办法找到这个节点。因此，堆的这种近乎无序的规则似乎毫无用处，不过对于快速移除最大节点的操作，以及快速插入新节点的操作，这种顺序已经足够了。这些操作是使用堆作为优先级队列所需要的全部操作。

6.移除操作：移除是指删掉关键字值最大的节点，即根节点。移除思路如下：

6.1.移走根，

6.2.把左后一个节点移到根的位置，

6.3.一直向下筛选这个节点，知道它在一个大于它的节点之下，小于它的节点之上为止。

6.4.过程图解： java数据结构----堆

说明：在被筛选节点的每个暂时停留的位置，向下筛选的算法总是要检查那一个子节点更大，然后目标节点和较大的子节点交换位置，如果要把目标节点和较小的子节点交换，那么这个子节点就会变成大子节点的父节点，这就违背了堆的条件。

7.堆的插入：插入使用向上筛选，节点最后插入到数组最后第一个空着的单元中，数组容量大小增加1。

7.1.插入图解： java数据结构----堆

说明：向上筛选的算法比向下筛选的算法相对简单，因为它不需要比较两个子节点关键字值的大小，节点只有一个父节点。目标节点主要和它的父亲节点换位即可。

7.2.不是真的交换： java数据结构----堆

8.用数组表示一棵树时，如果数组中节点的索引位x，则

a.它的父节点的下标是：(x-1)/2；

b.它的左子节点的下标为2*x + 1；

c.它的右子节点的下标是2*x + 2；

9.堆的代码：

9.1.Node.java

package com.cn.heap;
/**
* 堆的节点类
* @author Administrator
*
*/
public class Node {
private int iData;
public Node(int id){
   iData  = id;
}
public int getkey(){
   return iData;
}
public void setkey(int id){
   iData = id;
}
}

9.2.Heap.java

package com.cn.heap;
/**
* 堆的实现类
* @author Administrator
*
*/
public class Heap {
private Node[] heapArray;
private int maxSize;
private int currentSize;
public Heap(int mx){
   maxSize = mx;
   heapArray = new Node[maxSize];
   currentSize = 0;
}
public boolean isEmpty(){
   return currentSize == 0 ;
}
public boolean insert(int key){
   if (currentSize == maxSize)
       return false;
   Node thenode = new Node(key);
   heapArray[currentSize] = thenode;
   trickleUp(currentSize ++);
   return true;
}
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;
}
public Node remove(){
   Node root = heapArray[0];
   heapArray[0] = heapArray[-- currentSize];
   trickleDown(0);
   return root;
}
public void trickleDown(int index){
   int largeChild;
   Node top = heapArray[index];
   while (index < currentSize / 2){
       int leftChild = 2 * index + 1;
       int rightChild = 2 * index + 2;
       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];
       index = largeChild;
   }
   heapArray[index] = top;
}
public boolean change(int index,int newvalue){
   if (index < 0 || index >=currentSize)
       return false;
   int oldvalue = heapArray[index].getkey();
   heapArray[index].setkey(newvalue);
   if (oldvalue < newvalue)
       trickleUp(index);
   else
       trickleDown(index);
   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;
   int itemsPerrow = 1;
   int column = 0;
   int j = 0;
   String dots = "........................";
   System.out.println(dots + dots);
   while (currentSize > 0){
       if (column == 0)
           for (int i = 0; i < nBlanks; i++) {
               System.out.print(" ");
           }
       System.out.print(heapArray[j].getkey());
       if (++ j == currentSize)
           break;
       if (++ column == itemsPerrow){
           nBlanks /= 2;
           itemsPerrow *= 2;
           column = 0;
           System.out.println();
       }
       else
           for (int i = 0; i < nBlanks * 2 - 2; i++) 
               System.out.print(' ');
   }
   System.out.println("\n"+dots + dots);
}
}

9.3.HTest.java

package com.cn.heap;
/**
* heap类的测试
* @author Administrator
*
*/
public class HTest {
public static void main(String[] args) {
   Heap h = new Heap(10);
   h.insert(10);
   h.insert(30);
   h.insert(20);
   h.insert(18);
   h.insert(12);
   h.displayHeap();
   h.remove();
   h.displayHeap();
}
}

10.堆的效率：上述操作的时间复杂度是：O(logn)。

11.堆排序实现思路：使用insert()向堆中插入所有无序的数据项，然后重复使用remove()方法，就可以按序移除所有数据项，它的效率和快速排序类似，都是O(NlogN)，但快排稍微快些，因为堆插入时的向下筛选多出的比较所占用的时间。

11.1.Node.java

package com.cn.heap;
/**
* 堆的节点类
* @author Administrator
*
*/
public class Node {
private int iData;
public Node(int id){
   iData  = id;
}
public int getkey(){
   return iData;
}
public void setkey(int id){
   iData = id;
}
}

11.2.Heap.java

package com.cn.heap;
/**
* 堆的实现类
* @author Administrator
*
*/
public class Heap {
private Node[] heapArray;
private int maxSize;
private int currentSize;
public Heap(int mx){
   maxSize = mx;
   heapArray = new Node[maxSize];
   currentSize = 0;
}
public boolean isEmpty(){
   return currentSize == 0 ;
}
public boolean insert(int key){
   if (currentSize == maxSize)
       return false;
   Node thenode = new Node(key);
   heapArray[currentSize] = thenode;
   trickleUp(currentSize ++);
   return true;
}
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;
}
public Node remove(){
   Node root = heapArray[0];
   heapArray[0] = heapArray[-- currentSize];
   trickleDown(0);
   return root;
}
public void trickleDown(int index){
   int largeChild;
   Node top = heapArray[index];
   while (index < currentSize / 2){
       int leftChild = 2 * index + 1;
       int rightChild = 2 * index + 2;
       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];
       index = largeChild;
   }
   heapArray[index] = top;
}
public boolean change(int index,int newvalue){
   if (index < 0 || index >=currentSize)
       return false;
   int oldvalue = heapArray[index].getkey();
   heapArray[index].setkey(newvalue);
   if (oldvalue < newvalue)
       trickleUp(index);
   else
       trickleDown(index);
   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;
   int itemsPerrow = 1;
   int column = 0;
   int j = 0;
   String dots = "........................";
   System.out.println(dots + dots);
   while (currentSize > 0){
       if (column == 0)
           for (int i = 0; i < nBlanks; i++) {
               System.out.print(" ");
           }
       System.out.print(heapArray[j].getkey());
       if (++ j == currentSize)
           break;
       if (++ column == itemsPerrow){
           nBlanks /= 2;
           itemsPerrow *= 2;
           column = 0;
           System.out.println();
       }
       else
           for (int i = 0; i < nBlanks * 2 - 2; i++) 
               System.out.print(' ');
   }
   System.out.println("\n"+dots + dots);
}
public void displayArray(){
   for (int i = 0; i < maxSize; i++) 
       System.out.print(heapArray[i].getkey()+" ");
   System.out.println();
}
public void insertAt(int index,Node newnode){
   heapArray[index] = newnode;
}
public void incrementSize(){
   currentSize ++;
}
}

11.3.HeapSort.java

1package com.cn.heap;
 2 3import java.util.Scanner;
 4 5/** 6 * 基于堆的排序----堆排序
 7 * @author Administrator
 8 *
 9*/10publicclass HeapSort {
11publicstaticvoid main(String[] args) {
12int size,j;
13     Scanner in = new Scanner(System.in);
14     System.out.print("Enter number of items: ");
15     size = in.nextInt();
16     Heap theheap = new Heap(size);
17for (int i = 0; i < size; i++) {
18int random = (int)(Math.random()*100);
19         Node node = new Node(random);
20        theheap.insertAt(i, node);
21        theheap.incrementSize();
22    }
23     System.out.print("random: ");
24    theheap.displayArray();
25for (int i = size / 2 - 1; i >= 0; i --) {
26        theheap.trickleDown(i);
27    }
28     System.out.print("heap: ");
29    theheap.displayArray();
30    theheap.displayHeap();
31for (int i = size - 1; i >= 0; i --) {
32         Node node = theheap.remove();
33        theheap.insertAt(i,node);
34    }
35     System.out.print("sorted: ");
36    theheap.displayArray();
37}
38 }

参考：
https://www.cnblogs.com/g177w/p/8469399.html

数据结构数组

安科网

java数据结构----堆

ipqtjmqj

ipqtjmqj

相关推荐

比较JavaScript中的数据结构（数组与对象）

图解！24张图彻底弄懂九大常见数据结构！原创 Amazing10 业余码农 5月24日

java数据结构与算法一：稀疏数组

数据结构 & Java中的内存

详解Redis数据结构之跳跃表

数据结构之利用PHP实现二分搜索树

泛型和元编程的模型：Java, Go, Rust, Swift, D等

万能Python的秘诀：操纵数据的内置工具

Java实现单链表、栈、队列三种数据结构

Map和Set两种数据结构在ES6的作用

「算法与数据结构」带你看回溯算法之美

学c++需要先学c语言吗？

动图演示：手撸堆栈的两种实现方法！

技术人员思维和认知升级

python的链表基础知识点

数据结构 4

HBase/TiDB都在用的数据结构：LSM Tree，不得了解一下？

编写更简洁的Python代码的5个技巧

盘点 Python 10 大常用数据结构（下篇）

盘点 Python 10 大常用数据结构（上篇）

ipqtjmqj