java实现增强堆

java实现增强堆

什么是堆：
堆是一种重要的数据结构，构建堆的结构大致分为两种，分别是大根堆合小根堆。比如一颗完全二叉树，可以构建父节点大于所有字点的大根堆，也可以构建父节点小于所有子节点的小根堆。其实堆就是一颗完全二叉树，实现堆可以调整数组中当前节点i和i*2+1的位置与（i-1）/2的位置关系就好。

增强堆

增强堆就是在原来只有键的索引的基础上加入了值的索引，带有反向索引表的堆，代码如下。

package class06;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.linkedList;
import java.util.List;

import class05.code_heapSort;

public class HeapGreatertest {
	public class HeapGreater{
		private ArrayList heap;
		private HashMap indexMap;
		private int heapsize;
		private Comparator comp;
		
		public HeapGreater(Comparator c){
			heap = new ArrayList<>();
			indexMap = new HashMap<>();
			heapsize = 0;
			comp = c;
	
		}
		public boolean isEmpty() {
			return heapsize ==0;
		}
		public int size() {
			return heapsize;
		}
		public boolean contains(T obj) {
			return indexMap.containsKey(obj);
		}
		public T peek() {
			return heap.get(0);
		}
		public void push(T obj) {
			heap.add(obj);
			indexMap.put(obj, heapsize);
			heapInsert(heapsize++);
		}
		public T pop() {
			T ans = heap.get(0);
			swap(0,heapsize-1);
			indexMap.remove(ans);
			heap.remove(--heapsize);
			heapify(0);
			return ans;
		}
		public void remove (T obj) {
			T replace = heap.get(heapsize-1);
			int index = indexMap.get(obj);
			indexMap.remove(obj);
			heap.remove(--heapsize);
			if(obj!=replace) {
				heap.set(index, replace);
				indexMap.put(replace, index);
				resign(replace);
			}
		}
		private void resign(T obj) {
			heapInsert(indexMap.get(obj));
			heapify(indexMap.get(obj));
			
		}
		//返回堆上1所有元素
		public List getAllElements(){
			List ans = new ArrayList<>();
			for(T c : heap) {
				ans.add(c);
			}
			return ans;
		}
		
		
		private void heapify(int index) {
			int left = index*2+1;
			while(left
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5710364.html