Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3262512
  • 博文数量: 287
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2110
  • 用 户 组: 普通用户
  • 注册时间: 2019-10-28 13:40
文章分类

全部博文(287)

文章存档

2022年(60)

2021年(155)

2020年(50)

2019年(22)

我的朋友

分类: Java

2021-07-19 17:30:11

public class HeapNode{

    private int size;//堆大小

    private int[] heap;//保存堆数组

    //初始化堆

    public HeapNode(int n) {

        heap = new int[n];

        size = 0;

    }

    //小顶堆建堆

    public void minInsert(int key){

        int i = this.size;

        if (i==0) heap[0] = key;

        else {

            while (i>0 && heap[i/2]>key){

                heap[i] = heap[i/2];

                i = i/2;

            }

            heap[i] = key;

        }

        this.size++;

    }

    //大顶堆建堆

    public void maxInsert(int key){

        int i = this.size;

        if (i==0) heap[0] = key;

        else {

            while (i>0 && heap[i/2]

                heap[i] = heap[i/2];

                i = i/2;

            }

            heap[i] = key;

        }

        this.size++;

    }

    //小顶堆删除

    public int minDelete(){

        if (this.size==0) return -1;

        int top = heap[0];

        int last = heap[this.size-1];

        heap[0] = last;

        this.size--;

        //堆化

        minHeapify(0);

        return top;

    }

    //大顶堆删除

    public int maxDelete(){

        if (this.size==0) return -1;

        int top = heap[0];

        int last = heap[this.size-1];

        heap[0] = last;

        this.size--;

        //堆化

        maxHeapify(0);

        return top;

    }

    //小顶堆化

    public void minHeapify(int i){

        int L = 2*i,R=2*i+1,min;

        if (L<=size && heap[L] < heap[i]) min = L;

        else min = i;

        if (R <= size && heap[R] < heap[min]) min = R;

        if (min!=i){

            int t = heap[min];

            heap[min] = heap[i];

            heap[i] = t;

            minHeapify(min);

        }

    }

    //大顶堆化

    public void maxHeapify(int i){

        int L = 2*i,R=2*i+1,max;

        if (L<=size && heap[L] > heap[i]) max = L;

        else max = i;

        if (R <= size && heap[R] > heap[max]) max = R;

        if (max!=i){

            int t = heap[max];

            heap[max] = heap[i];

            heap[i] = t;

            maxHeapify(max);

        }

    }

    //输出堆

    public void print(){

        for (int i = 0; i < this.size; i++) {

            System.out.print(heap[i]+" ");

        }

        System.out.println();

    }

}

阅读(1036) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~