java利用Heap堆实现PriorityQueue优先队列

本篇内容介绍了“java利用Heap堆实现PriorityQueue优先队列”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

首先做一个优先队列的接口：

import java.util.List;
public interface PriorityQueue {
 void add(Object o);
 void addAll(List elements);
 Object remove(); 
 boolean isEmpty();
 int size();
}

接下来，用java写一个heap结构，实现priority queue接口：

heap是一种二叉树，所遵守的唯一规律为：所有的子节点都要大于（小于）父节点。

增加一个节点，直接加在最后，然后用upheap排序

删除一个节点，则把要删除的节点与跟节点交换，然后删除交换后的根节点（既最后一个点），然后用downheap重新排序

heap的add方法很简单，关键是addall，根据是空heap或非空，，应有不同的算法以保证效率，空heap用bottom－up排序应该是最快的，至于非空的heap，则比较有挑战性，以下是我自己写的一段程序，仅供参考：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Arrays;

public class Heap implements PriorityQueue {

        protected Comparator comparator;

        final static int ROOT_INDEX = 0;
        final static int PRE_ROOT_INDEX = ROOT_INDEX - 1;

        List heap;

        public Heap() {
                heap = new ArrayList();
        }

        public Heap(Comparator c) {
                heap = new ArrayList();
                comparator = c;
        }

        /* (non-Javadoc)
         * @see PriorityQueue#add(java.lang.Object)
         */
        public void add(Object o) {
                heap.add(o);

                int index = heap.size() - 1;
                while (index > ROOT_INDEX) {
                        index = stepUpHeap(index);
                }
        }

        /**
         * Enforce ordering for heap element and its parent.
         * Indices start from ROOT_INDEX (inclusive).
         * @param index valid non-root heap position
         * @return index of parent in heap, if swap occurs, otherwise ROOT_INDEX
         */
        protected int stepUpHeap(int index) {
                int parentIndex = parent(index);
                Object element = heap.get(index);
                Object parent  = heap.get(parentIndex);
                if (compare(parent, element) > 0) {     // heap is out of order here
                        heap.set(parentIndex, element);
                        heap.set(index, parent);
                        return parentIndex;           // jump to parent of index
                } else                                  // heap is OK
                        return ROOT_INDEX;              // so jump to root
        }

        /**
         * Compare elements using comparator if it exists.
         * Otherwise assume elements are Comparable
         * @param element
         * @param other
         * @return result of comparing element with other
         */
        protected int compare(Object element, Object other) {
                if (comparator == null) {
                        Comparable e = (Comparable) element;
                        Comparable o = (Comparable) other;
                        return e.compareTo(o);
                } else
                        return comparator.compare(element, other);
        }

        /**
         * Index of parent in heap.
         * @param index to find parent of
         * @return index of parent
         */
        protected int parent(int index) {
                return (index - PRE_ROOT_INDEX) / 2 + PRE_ROOT_INDEX;
        }

        public String toString() {
                return heap.toString();
        }

        /* (non-Javadoc)
         * @see PriorityQueue#isEmpty()
         */
        public boolean isEmpty() {
                return heap.isEmpty();
        }

        /* (non-Javadoc)
         * @see PriorityQueue#size()
         */
        public int size() {
                return heap.size();
        }

        /* (non-Javadoc)
         * @see PriorityQueue#remove()
         */
        public Object remove() throws RuntimeException{
                if (isEmpty())
                        throw new RuntimeException();

                int index = heap.size() - 1;
                Object least;
                if(index==0){
                        least = heap.get(index);
                        heap.remove(index);
                }
                else{
                        Object element = heap.get(index);
                        least  = heap.get(ROOT_INDEX);
                        heap.set(ROOT_INDEX, element);
                        heap.set(index, least);
                        heap.remove(index);
                        stepDownHeap(ROOT_INDEX);
                }
                return least;
        }

        /* (non-Javadoc)
         * @see PriorityQueue#addAll(java.util.List)
         */
        public void addAll(List elements) {
                int numbers = elements.size();
                for(int i=0;i<numbers;i++)
                        heap.add(elements.get(i));

                int n=1,rows=0;
                for(rows=0;n<= heap.size();rows++){
                        n = n*2;
                        }
                for(int i=rows-1;i>=1;i--){
                        for(int j=(int)(Math.pow(2,i-1)-1);j<=(int)(Math.pow(2,i)-2);j++){
                                stepDownHeap(j);
                        }
                }

        }

        public static void sort(Comparable[] data) {
                Heap cpr = new Heap();
                List middle = Arrays.asList(data);
                cpr.addAll(middle);
                for(int i=data.length-1;i>=0;i--)
                        data[i] = (Comparable)(cpr.remove());
        }

        public static void sort(Object[] data, Comparator c) {
                Heap cpr = new Heap(c);
                List middle = Arrays.asList(data);
                cpr.addAll(middle);
                for(int i=data.length-1;i>=0;i--)
                        data[i] = cpr.remove();
        }

        public void stepDownHeap(int index){
                int p = index;
                int c = 2*p + 1;
                Object temp = heap.get(p);
                while(c<heap.size()){
                        if(c+1<heap.size() && compare(heap.get(c+1),heap.get(c))<0)
                                c = c + 1;
                        if(compare(temp,heap.get(c))<=0)
                                break;
                        else {
                                heap.set(p,heap.get(c));
                                p = c;
                                c = 2*p + 1;
                                }
                }
                heap.set(p,temp);
        }
}

最后是一段测试程序：

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class PQTest {
 
 ///////////////////////////////////////////////////////
 //
 // static declarations
 //
 ///////////////////////////////////////////////////////
 
 public static void main(String[] args) {
  PQTest test = new PQTest();
  test.constructor();
  test.add();
  test.remove();
  test.addAll();
  test.sort();
 }

 static int nextIndex;
 final static long SEED = 88888L;
 final static Random random = new Random(SEED);

 static Integer[] arrayData;  // backing store for data
 static List data;

 static void makeData(int n) {
  random.setSeed(SEED);
  arrayData = new Integer[n];
  for (int i = 0; i < n; ++i) {
   arrayData[i] = (new Integer(i));
  }
  data = Arrays.asList(arrayData);
  Collections.shuffle(data, random);
 }
 
 static void testAssert(boolean b, String s) {
  if (!b) throw new RuntimeException(s);
 }
 
 static Comparator comparableComparator() {
  return new Comparator() {
   public int compare(Object x, Object y) {
    return ((Comparable) x).compareTo(y);
   }
  };
 }
 
 static Comparator reverseComparator(Comparator c) {
  return new ReverseComparator(c);
 }
 
 static class ReverseComparator implements Comparator {
  Comparator c;
  ReverseComparator(Comparator c) {
   this.c = c;
  }
  public int compare(Object x, Object y) {
   return - c.compare(x,y);
  }
 }
 
 static CountComparator countComparator(Comparator c) {
  return new CountComparator(c);
 }

 static class CountComparator implements Comparator {
  Comparator c;
  CountComparator(Comparator c) {
   this.c = c;
  }
  int count = 0;
  public int getCount() {
   return count;
  }
  public void clearCount() {
   count = 0;
  }
  public int compare(Object x, Object y) {
   ++count;
   return c.compare(x,y);
  }
 }
 
 ///////////////////////////////////////////////////////
 //
 // instance specific declarations
 //
 ///////////////////////////////////////////////////////
  
 // instance variable
 
 PriorityQueue pq; // priority queue to be tested
 Comparator c;

 // instance methods for testing priority queue operation
 
 void constructor() {
  System.out.println("new Heap()");
  pq = new Heap();
  checkPQ(true, 0);
  System.out.println();
 }

 void add() {
  makeData(16);
  for (int i = 0; i < 16; ++i) {
   Object o = data.get(i);
   System.out.println("add(" + o + ") ...");
   pq.add(o);
   checkPQ(false, i+1);
  }
  System.out.println();
 }
 
 void remove() {
  for (int i = pq.size(); i > 0; --i) {
   checkPQ(false, i);
   System.out.print("remove() = ");
   Object o = pq.remove();
   System.out.println(o);
  }
  checkPQ(true, 0);
  System.out.println();
 }

 void addAll() {
  c = countComparator(comparableComparator());
  pq = new Heap(c);
  makeData(99);
  addN(0,16);
  addN(16,16);
  addN(16,17);
  addN(17,19);
  addN(19,27);
  addN(27,43);
  addN(43,48);
  addN(48,99);
  System.out.println();
 }

 void addN(int from, int to) {
  int size = pq.size();
  List dataN = data.subList(from,to);
  int n = to - from;
  System.out.println("addAll(" + dataN + ") ... " + n + " items ...");
  pq.addAll(dataN);
  checkPQ(false, size+n);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  ((CountComparator) c).clearCount();
 }

 void sort() {
  Comparator c = null;
  
  System.out.println("Testing sort() with natural ordering");  
  sortWithComparator(c);
  System.out.println();

  System.out.println("Testing sort() with reverse natural ordering"); 
  c = reverseComparator(comparableComparator());
  sortWithComparator(c);
  System.out.println();

  System.out.println("Testing sort() with natural ordering and comparison count");  
  c = countComparator(comparableComparator());
  sortWithComparator(c);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  System.out.println();

  System.out.println("Testing sort() with reverse natural ordering and comparison count");  
  c = countComparator(reverseComparator(comparableComparator()));
  sortWithComparator(c);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  System.out.println();  
 }

 void sortWithComparator(Comparator c) {
  makeData(64);
  System.out.println("Unsorted: " + data);
  Heap.sort(arrayData, c);
  System.out.println("Sorted:   " + data);
  System.out.println();
 }

 // helper methods

 void checkPQ(boolean isEmpty, int size) {
  System.out.println("PriorityQueue: " + pq);
  testAssert(pq.isEmpty() == isEmpty,  "isEmpty()");
  testAssert(pq.size() == size,  "size()");
 }
}

对于非空的heap，应该有更快的算法（但是效率都是o（nlogn）），只是结果可能会有所不同，但是仍然是按照heap的排序规则排列。

[@more@]

“java利用Heap堆实现PriorityQueue优先队列”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！