bool 里的 输入 default main system heap move parent
用堆实现优先级队列,插入和删除都很快o(logN)
编程语言中的内存堆与这里的数据结构是不一样的
堆:一种树(特殊的二叉树)
特点:它是完全二叉树,除了树的最后一层节点不需要是满,其他的每一层从左到右都完全是满的。
它常常是用一个数组实现
堆中的每一个节点都满足堆的条件,父节点的关键字要大于所有子节点。
堆是弱序(遍历不适合)
插入:获取一个节点,放入完全二叉树中。与其父节点作比较,替换(完成父节点的关键字要大于子节点)
删除:删除顶端节点,将最后一个叶子节点赋值为顶点节点。然后移动 完成父节点的关键字要大于子节点。
改变节点优先级:将该节点的值更换。然后将它放在合适的位置(完成父节点的关键字要大于子节点)
(父节点的关键字要大于所有子节点,即三个点之间选取最大的与临时父节点替换)
- public class Node {
- private int iData; //既是关键字,又是数值
- public Node(int key) { //初始化
- iData = key;
- }
- public int getKey() { //访问关键字
- return iData;
- }
- public void setKey(int id) { //改变关键字
- iData = id;
- }
- }
- //建立堆
- public class Heap {
- private Node[] heapArray;//存储节点的数组
- private int maxSize;//总大小
- private int currentSize;//当前堆的大小
- public Heap(int mx) {
- maxSize=mx;//初始化总大小
- currentSize=0;//初始化当前数据大小0
- heapArray=new Node[maxSize];
- }
- //判断是否为空
- public boolean isEmpty() {
- return currentSize==0;
- }
- //增加(判断为满,则不能新增)
- public boolean insert(int key) {
- if(currentSize==maxSize)
- return false;
- Node newNode=new Node(key);//建立key节点
- heapArray[currentSize]=newNode;//将key节点插入数组的最末
- //(向上调整)完成堆的规则(父节点大于子节点)
- trickleUP(currentSize);
- currentSize++;//增加成功,数量加1
- 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 rightChile=leftChild+1; //右子节点
- if(rightChile<currentSize && heapArray[leftChild].getKey()<heapArray[rightChile].getKey())//有右子节点
- largeChild=rightChile;
- else
- largeChild=leftChild;
- if(top.getKey()>=heapArray[largeChild].getKey())
- break;
- heapArray[index]=heapArray[largeChild];//将大的关键字调整
- index=largeChild;
- }
- //最后定位Node top=heapArray[index]
- 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.println("堆数组");
- for(int m=0;m<currentSize;m++)
- if(heapArray[m]!=null)
- System.out.print(heapArray[m].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 k=0;k<nBlanks;k++)
- 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 k=0;k<nBlanks*2-2;k++)
- System.out.print(‘ ‘);
- }
- System.out.println("\n"+dots+dots);
- }
- }
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- public class Test {
- public static void main(String[] agrs) throws IOException {
- int value,
- value2;
- Heap theHeap = new Heap(31);
- boolean success;
- theHeap.insert(70);
- 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) {
- System.out.println("Enter first letter of show ,insert,remove,change:");
- int choice = getChar();
- switch (choice) {
- case‘s‘:
- theHeap.displayHeap();
- break;
- case‘i‘:
- System.out.print("enter value");
- value = getInt();
- success = theHeap.insert(value);
- if (!success) System.out.println("man le");
- break;
- case‘r‘:
- if (!theHeap.isEmpty()) theHeap.remove();
- else System.out.println("不能删除");
- break;
- case‘c‘:
- System.out.println("输入要改变的索引");
- value = getInt();
- System.out.println("输入要改变的值");
- value2 = getInt();
- success = theHeap.change(value, value2);
- if (!success) System.out.println("无效的索引");
- break;
- default:
- System.out.println("无效的输入");
- }
- }
- }
- public static String getString() throws IOException {
- InputStreamReader isr = new InputStreamReader(System. in );
- BufferedReader br = new BufferedReader(isr);
- return br.readLine();
- }
- public static char getChar() throws IOException {
- return getString().charAt(0);
- }
- public static int getInt() throws IOException {
- return Integer.parseInt(getString());
- }
- }
堆(插入删除)
来源: http://www.bubuko.com/infodetail-2361913.html