详解Java如何实现小顶堆和大顶堆

详解Java如何实现小顶堆和大顶堆

大顶堆

每个结点的值都大于或等于其左右孩子结点的值

小顶堆

每个结点的值都小于或等于其左右孩子结点的值

对比图

实现代码

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();

}

}

测试

public class Heap {

static int[] a = {5,3,6,4,2,1};

static int n = a.length;

public static void main(String[] args){

HeapNode heapNode = new HeapNode(n);

for (int i = 0; i < n; i++) {

heapNode.maxInsert(a[i]);

}

heapNode.print();

for (int i = 0; i < n; i++) {

int min = heapNode.maxDelete();

System.out.print("堆顶："+min+" 剩下堆元素：");

heapNode.print();

}

}

}

结果

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();

}

}

测试

public class Heap {

static int[] a = {5,3,6,4,2,1};

static int n = a.length;

public static void main(String[] args){

HeapNode heapNode = new HeapNode(n);

for (int i = 0; i < n; i++) {

heapNode.maxInsert(a[i]);

}

heapNode.print();

for (int i = 0; i < n; i++) {

int min = heapNode.maxDelete();

System.out.print("堆顶："+min+" 剩下堆元素：");

heapNode.print();

}

}

}

结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。