堆、队列、优先队列底层实现

骑猪看日落 2024-02-18 21:11 51阅读 0赞

1、通过ArrayList实现大根堆：

堆：有大根堆和小根堆，对于大根堆来说，其左右子元素比根元素小

1）添加操作：首先将它添加到堆的末尾，然后按以下方式建树：

将最后一个结点作为当前结点

while(当前结点大于它的父节点)\{

将当前结点和它的父结点交换；

现在当前结点往上进一个层次；

2）删除操作：删除之后将最后一个结点成为当前根结点，然后维护该数，其余操作和添加操作类似

package shixian;
    
    import java.util.ArrayList;
    
    /**大根堆*/
    public class Heap<E extends Comparable<E>> {
         private ArrayList<E> list = new ArrayList<>();  //用数组实现堆
         
         public Heap() {
        	 
         }
         
         public Heap(E[] objects) {
        	 for(int i = 0; i < objects.length; i++)
        		 list.add(objects[i]);
         }
         
         /**添加一个元素*/
         public void add(E e) {
        	 list.add(e);
        	 int currentIndex = list.size() - 1;
        	 
        	 while(currentIndex > 0) {
        		 int parentIndex = (currentIndex - 1)/2; //找到父节点
        		 if(list.get(currentIndex).compareTo(list.get(parentIndex)) > 0 ) {//大于父节点
        			 E temp = list.get(currentIndex);
        			 list.set(currentIndex, list.get(parentIndex));
        			 list.set(parentIndex, temp);
        		 }else 
        			 break;
        		 currentIndex = parentIndex;
        	 }
         }
      
      
         /**删除并返回根节点，然后维护大根堆*/
         public E remove() {
        	 if(list.size() == 0) return null;
        	 
        	 E root = list.get(0);
        	 list.set(0, list.get(list.size() - 1)); // 将最后一个节点放在根结点
        	 list.remove(list.size() - 1);
        	 
        	 int currentIndex = 0;
        	 while(currentIndex < list.size()) {
        		 int leftChildIndex = 2 * currentIndex + 1;
        		 int rigthChildIndex = 2 * currentIndex + 2;
        		 if(leftChildIndex >= list.size()) break;
        		 //选择左右子结点的大者
        		 int maxIndex = leftChildIndex;
        		 if(rigthChildIndex < list.size()) {
        			 if(list.get(maxIndex).compareTo(list.get(rigthChildIndex)) < 0) {
        				 maxIndex = rigthChildIndex;
        			 }
        		 }
        		 
        		 //将左右结点中的大者与当前节点比较
        		 if(list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
        			 E temp = list.get(maxIndex);
        			 list.set(maxIndex, list.get(currentIndex));
        			 list.set(currentIndex, temp);
        			 currentIndex = maxIndex;
        		 }else {
        			 break;
        		 }
        	 }
        	 return root;
         }    
         
         public int getSize() {
        	 return list.size();
         }
    }

\-----------------------------------------------------------------------

2、队列：使用链表实现队列

package shixian;
    
    public class GenericQueue<E> {
       private java.util.LinkedList<E> list =
    		   new java.util.LinkedList<>();
       
       /**添加一个元素到该队列*/
       public void enqueue(E e) {  
    	   list.addLast(e);
       }
       
       /**从队列删除一个元素*/
       public E dequeue() {
    	   return list.removeFirst();
       }
       
       /**返回队列中元素的数目*/
       public int getSize() {
    	   return list.size();
       }
       
       @Override
       public String toString() {
    	   return "Queue: "+list.toString();
       }
    }

测试;

package shixian;
    
    public class TestQueue {
    
    	public static void main(String[] args) {
            GenericQueue<String> queue = new GenericQueue<>();
            
            queue.enqueue("Tom");
            System.out.println("(1) "+queue);
            
            queue.enqueue("Susan");
            System.out.println("(2) "+queue);
            
            queue.enqueue("Kim");
            queue.enqueue("Michael");
            System.out.println("(3) "+queue);
            
            System.out.println("(4) "+queue.dequeue());
            System.out.println("(5) "+queue.dequeue());
            System.out.println("(6) "+queue);
    	}
    
    }
    
    
    /**
     * 输出
    (1) Queue: [Tom]
    (2) Queue: [Tom, Susan]
    (3) Queue: [Tom, Susan, Kim, Michael]
    (4) Tom
    (5) Susan
    (6) Queue: [Kim, Michael]
    
     * */

\----------------------------------------------------------

3、优先队列：使用堆实现

package shixian;
    
    /**用堆实现优先队列*/
    public class MyPriorityQueue<E extends Comparable<E>> {
          private Heap<E> heap = new Heap<>();
          
          /**添加元素*/
          public void enqueue(E e) {
        	  heap.add(e);
          }
          
          /**删除队首元素*/
          public E dequeue() {
        	  return heap.remove();
          }
          
          public int getSize() {
        	  return heap.getSize();
          }
    }

测试：

package shixian;
    
    public class TestPriorityQueue {
    
    	public static void main(String[] args) {
    		Patient patient1 = new Patient("John",2);
    		Patient patient2 = new Patient("Jim",1);
    		Patient patient3 = new Patient("Tim",5);
    		Patient patient4 = new Patient("Cindy",7);
    		
    		MyPriorityQueue<Patient> priorityQueue = 
    				new MyPriorityQueue<>();
    		priorityQueue.enqueue(patient1);
    		priorityQueue.enqueue(patient2);
    		priorityQueue.enqueue(patient3);
    		priorityQueue.enqueue(patient4);
    		
    		while (priorityQueue.getSize() > 0) {
    			System.out.println(priorityQueue.dequeue() + " ");
    		}
    	}
    
    	
    	static class Patient implements Comparable<Patient>{
            private String name;
            private int priority;
            
            public Patient(String name,int priority) {
    			this.name = name;
    			this.priority = priority;
    		}
            
            @Override
            public String toString() {
            	return name + "(priority:" + priority + ")";
            }
            
    		@Override
    		public int compareTo(Patient patient) {
    			return this.priority - patient.priority;
    		}
    		
    	}
    }
    
    /**
     *输出
    Cindy(priority:7) 
    Tim(priority:5) 
    John(priority:2) 
    Jim(priority:1) 
     * */