首页 > 编程语言 > 详细

数据结构与算法-优先级队列

时间:2020-08-15 13:20:22      阅读:78      评论:0      收藏:0      [点我收藏+]

优先级队列

概念

搜索树结构和词典结构,都支持覆盖数据全集的访问和操作。也就是说,其中存储的每一数据对象都可作为查找和访问目标
优先级队列,较之此前的数据结构反而有所削弱。具体地,这类结构将操作对象限定于当前的全局极值者。而维护一个偏序关系

  • 接口
template <typename T> struct PQ {
	//优先级队列PQ模板类
	virtual void insert ( T ) = 0;
	//按照比较器确定的优先级次序插入词条
	virtual T getMax() = 0;
	//叏出优先级最高的词条
	virtual T delMax() = 0;
	//删除除优先级最高的词条

};
  • 应用
/******************************************************************************************
2 * Huffman树极造算法:对传入癿Huffman森枃forest逐步合幵,直刡成为一棵树
3 ******************************************************************************************
4 * forest基亍优先级队列实现,此算法适用亍符合PQ接口癿仸何实现斱式
5 * 为Huffman_PQ_List、Huffman_PQ_ComplHeap和Huffman_PQ_LeftHeap共用
6 * 编译前对应工程叧需讴置相应标志:DSA_PQ_List、DSA_PQ_ComplHeap戒DSA_PQ_LeftHeap
7 ******************************************************************************************/
HuffTree* generateTree ( HuffForest* forest ) {
	while ( 1 < forest->size() ) {
		HuffTree* s1 = forest->delMax();
		HuffTree* s2 = forest->delMax();
		HuffTree* s = new HuffTree();
		s->insertAsRoot ( Huffchar ( ‘^‘, s1->root()->data.weight + s2->root()->data.weight ) );
		s->attachAsLC ( s->root(), s1 );
		s->attachAsRC ( s->root(), s2 );
		forest->insert ( s );
		//将合幵后癿Huffman树揑回Huffman森枃
	}
	HuffTree* tree = forest->delMax();
	//至此,森枃中癿最后一棵树
	return tree;
	//即全尿Huffman编码树
}

完全二叉堆

  1. 什么是堆
    技术分享图片
  • 它是一个完全二叉树,即除了最后一层节点不是满的,其他层节点都是满的,即左右节点都有。

  • 它不是二叉搜索树,即左节点的值都比父节点值小,右节点的值都不比父节点值小,这样查找的时候,就可以通过二分的方式,效率是(log N)。

  • 它是特殊的二叉树,它要求父节点的值不能小于子节点的值。这样保证大的值在上面,小的值在下面。所以堆遍历和查找都是低效的,因为我们只知道从根节点到子叶节点的每条路径都是降序的,但是各个路径之间都是没有联系的,查找一个值时,你不知道应该从左节点查找还是从右节点开始查找。

  • 它可以实现快速的插入和删除,效率都在(log N)左右。所以它可以实现优先级队列。
    技术分享图片

  1. 大顶堆与小顶堆
    堆序性也可对称地约定为“堆顶以外的每个节点都不低(小)于其父节点”,此时同理,优先级最低的词条,必然始终处于堆顶位置。为以示区别,通常称前(后)者为大(小)顶堆

  2. 模板类与一些常用方法

//必要的方法
int Parent(int i){
	//PQ[i]的父节点(floor((i-1)/2),i无论正负)
	return ((i - 1) >> 1);
}
int LChild(int i){
	//PQ[i]的左孩子
	return (1 + (i << 1));
}
int RChild(int i){
	//PQ[i]的右孩子
	return ((i + 1) << 1);
}
Boolean InHeap(int n,int i){
	//判断PQ[i]是否合法
	return ((-1 < i) && (i < n));
}
Boolean ParentValid(int i){
	return (Parent(i) >= 0);
}
Boolean LChildValid(int n,int i){
	//判断PQ[i]是否有一个(左)孩子
	return InHeap(n,LChild(i));
}
Boolean RChildValid(int n,int i){
	//判断PQ[i]是否有两个孩子
	return InHeap(n,RChild(i));
}
int Bigger(Vector<T> PQ,int i,int j){
	//取大者(等时前者优先)
	return (lt(PQ.elementAt(i),PQ.elementAt(j)) ? j : i);
}
int ProperParent(Vector<T> PQ,int n, int i){
	/*父子(至多)三者中的大者*/
	return (RChildValid(n,i) ? Bigger(PQ,Bigger(PQ,i,LChild(i)),RChild(i)) :
	                (LChildValid(n,i) ? Bigger(PQ,i,LChild(i)) : i));
}
//相等时父节点优先,如此可避免不必要的交换
Boolean lt(T a,T b){
	return ((int)a > (int)b);
}
void swap(T a,T b){
	T c = a;
	a = b;
	b = c;
}
void copyFrom(T[] A,int lo,int hi){
	int i = 0;
	while (lo < hi){
		this.set(i++, A[lo++]);
	}
}
int LastInternal(int n){
	return ((n + 1) / 2 - 1);
}

技术分享图片

元素插入

  • 原理
    技术分享图片

  • 实现

@Override
    public void insert(T e) {
	//插入词条
	this.addElement(e);
	percolateUp(elementCount - 1);
}
protected int percolateUp(int i){
	//上滤
	while (ParentValid(i)){
		int j = Parent(i);
		if (lt(elementAt(i),elementAt(j))) break;
		swap(elementAt(i),elementAt(j));
		i = j;
	}
	return i;
}
  • 实例
    技术分享图片

元素删除

  • 原理
    技术分享图片

  • 实现

@Override
    public T delMax() {
	//删除词条
	T maxElem = elementAt(0);
	this.setElementAt(elementAt(elementCount - 1),0);
	this.remove(--elementCount);
	percolateDown(elementCount,0);
	return maxElem;
}
protected int percolateDown(int n,int i){
	//下滤
	int j = 0;
	while (i != (j = ProperParent(this,n,j))){
		swap(elementAt(i),elementAt(j));
		i = j;
	}
	return i;
}
  • 实例
    技术分享图片

批量建堆

  • 原理
    技术分享图片

  • 实现

public  PQ_CompHeap(T[] A, int n){
	//批量构造
	copyFrom(A,0,n);
	heapify(n);
}
protected void heapify(int n){
	//Floyd建堆算法
	for (int i = LastInternal(n);i >= 0;i--){
		//自下而上,依次
		percolateDown(n,i);
		//下滤各内部节点
	}
}
protected int percolateDown(int n,int i){
	//下滤
	int j = 0;
	while (i != (j = ProperParent(this,n,j))){
		swap(elementAt(i),elementAt(j));
		i = j;
	}
	return i;
}
  • 实例
    技术分享图片

就地堆排序

  • 原理
    技术分享图片

  • 实现

//堆排序
public void heapSort(T[] A,int lo,int hi){
	copyFrom(A,lo,hi);
	int n = hi - lo;
	heapify(n);
	while (0 < --n){
		swap(A[0],A[n]);
		percolateDown(n,0);
	}
}
  • 实例
    技术分享图片

技术分享图片

左视堆

概念

对于堆的合并来说,可以想到的有两种方法:

  • 简单的取出并插入

  • 将两个堆中词条视为无顺序的,用堆合并
    技术分享图片

  • 堆不需要与二叉树一样保持平衡
    左视堆:左式堆是优先级队列的另一实现方式,可高效地支持堆合并操作。其基本思路是:在保持堆序性的前提下附加新的条件,使得在堆的合并过程中,只需调整很少量的节点。具体地,需参与调整的节点不超过O(logn)个,故可达到极高的效率。
    技术分享图片

模板类

使用的是二叉树结构
技术分享图片

空节点路径长度
技术分享图片

左倾性
技术分享图片

最右侧通路
技术分享图片

package com.atguigu.domin;
import com.atguigu.self.BinNode;
import com.atguigu.self.BinTree;
/**
 * @anthor shkstart
 * @create 2020-08-13 15:07
 */
public class PQ_LeftHeap<T> extends BinTree<T> implements PQ<T> {
	@Override
	    public void insert(T e) {
		//插入元素
		BinNode<T> v = new BinNode<T>(e);
		_root = merge(_root,v);
		_root.parent = null;
		_size++;
	}
	@Override
	    public T getMax() {
		//取出优先级最高的元素
		return _root.data;
	}
	@Override
	    public T delMax() {
		//删除优先级最高的元素
		BinNode<T> lHeap = _root.lc;
		//左子堆
		BinNode<T> rHeap = _root.rc;
		//右子堆
		T e = _root.data;
		//备份堆顶处的最大元素
		_size--;
		//删除一个节点
		_root = merge(lHeap,rHeap);
		//原左右堆合并
		if (_root != null){
			//更新父子链接
			_root.parent = null;
		}
		return e;
		//返回源节点处数据
	}
	public BinNode<T> merge(BinNode<T> a, BinNode<T> b){
		if (a ==null) return b;
		if (b == null) return a;
		if (lt(a.data,b.data)) swap(b,a);
		a.rc = merge(a.rc,b);
		a.rc.parent = a;
		if (a.rc == null || a.rc.npl < a.rc.npl){
			swap(a.lc,a.rc);
		}
		a.npl = (a.rc != null) ? a.rc.npl + 1:1;
		return a;
	}
	//一些必要的方法
	void swap(BinNode<T> a,BinNode<T> b){
		BinNode<T> c = a;
		a = b;
		b = c;
	}
	Boolean lt(T a,T b){
		return ((int)a < (int)b);
	}
}

合并

  • 原理
    技术分享图片

技术分享图片

  • 实现
public BinNode<T> merge(BinNode<T> a, BinNode<T> b){
	if (a ==null) return b;
	if (b == null) return a;
	if (lt(a.data,b.data)) swap(b,a);
	a.rc = merge(a.rc,b);
	a.rc.parent = a;
	if (a.rc == null || a.rc.npl < a.rc.npl){
		swap(a.lc,a.rc);
	}
	a.npl = (a.rc != null) ? a.rc.npl + 1:1;
	return a;
}
//一些必要的方法
void swap(BinNode<T> a,BinNode<T> b){
	BinNode<T> c = a;
	a = b;
	b = c;
}
Boolean lt(T a,T b){
	return ((int)a < (int)b);
}
  • 实例
    技术分享图片

技术分享图片

基于合并的插入和删除

  • 原理
    技术分享图片

技术分享图片

  • 实现
@Override
    public void insert(T e) {
	//插入元素
	BinNode<T> v = new BinNode<T>(e);
	_root = merge(_root,v);
	_root.parent = null;
	_size++;
}
@Override
    public T getMax() {
	//取出优先级最高的元素
	return _root.data;
}
@Override
    public T delMax() {
	//删除优先级最高的元素
	BinNode<T> lHeap = _root.lc;
	//左子堆
	BinNode<T> rHeap = _root.rc;
	//右子堆
	T e = _root.data;
	//备份堆顶处的最大元素
	_size--;
	//删除一个节点
	_root = merge(lHeap,rHeap);
	//原左右堆合并
	if (_root != null){
		//更新父子链接
		_root.parent = null;
	}
	return e;
	//返回源节点处数据
}
  • 实例
    技术分享图片

技术分享图片

锦标赛排序

原始算法

  • 原理
    技术分享图片

  • 实现

相关链接

https://www.cnblogs.com/binarylei/p/10115921.html#24-堆排序-vs-快速排序

package com.atguigu.domin;
/**
 * @anthor shkstart
 * @create 2020-08-13 16:31
 */
public class TourSort extends PQ_CompHeap{
	public  static final int MAX = 10000;
	private class Node//用node来存储竞赛排序过程中的节点,包括里面的数据和数据在数组中的ID
	{
		public int data;
		public int id;
		public Node()
		        {
		}
		public Node(int data, int id) {
			this.data = data;
			this.id = id;
		}
	}
	public void Adjust(Node[] B, int idx){
		//当去除最小元素以后,我们要调整数组
		while (idx != 0){
			if (idx / 2 == 0){
				if (B[idx].id == -1){
					B[Parent(idx)] = B[idx + 1];
				} else {
					B[Parent(idx)] = B[idx].data > B[idx+1].data ? B[idx+1] : B[idx];
				}
			} else {
				if (B[idx].id == -1){
					B[Parent(idx)] = B[idx - 1];
				} else {
					B[Parent(idx)] = B[idx].data > B[idx-1].data ? B[idx-1] : B[idx];
				}
			}
		}
	}
	public void creat(int[] A) {
		int n = 1;
		while (n < A.length){
			n *= 2;
		}
		int s = n - 1;
		Node[] B = new Node[2*n - 1];
		for (int i = 0;i < n;i++){
			if (i < A.length){
				B[n - 1 + i].data = A[i];
				B[n - 1 + i].id =n - 1 + i;
			} else {
				B[n - 1 + i].data = MAX;
				B[n - 1 + i].id = -1;
			}
		}
		while (--s >= 0){
			if (B[LChild(s)].id == (-1)) {
				B[s] = B[RChild(s)];
			} else if (B[RChild(s)].id == (-1)) {
				B[s] = B[LChild(s)];
			} else {
				B[s] = (B[LChild(s)].data < B[RChild(s)].data) ? B[LChild(s)] : B[RChild(s)];
			}
		}
		for ( int i = 0; i < A.length; i++)//实际排序的过程
		{
			A[i] = B[0].data;
			//取出最小的
			B[B[0].id].id = -1;
			Adjust(B, B[0].id);
		}
	}
}

改进算法

  • 原理
    技术分享图片

  • 实现(还未写)

多叉堆

  • 原理
    技术分享图片

  • 效率
    技术分享图片

技术分享图片

  • 实现(还未写)

相关链接

HashTable解析(先写到这里,等hashmap看了整理到一起)


package java.util;

import java.io.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
import java.util.function.Function;
import java.util.function.BiFunction;

/*

和HashMap一样,Hashtable 也是一个散列表,它存储的内容是键值对(key-value)映射。
Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 的函数都是同步的,这意味着它是线程安全的。它的key、value都不可以为null。
此外,Hashtable中的映射不是有序的。
*/

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    /**
     * hashtable中的数据
     */
    private transient Entry<?,?>[] table;

    /**
     * 表中的元素的实际数量
     */
    private transient int count;

    /**
     * 阈值,判断是否需要调整容量
     */
    private int threshold;

    /**
     * 加载因子,一般0.75
	 */
    private float loadFactor;

    /**
     *对于表的操作次数,可以判断
	 *是否有并发线程对其进行改动,并返回错误
     */
    private transient int modCount = 0;

    /**
	*版本号
	*/
    private static final long serialVersionUID = 1421746759512286392L;

    /**
     * 构造器:有初始容量和加载因子
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;//以上是对极端情况的调整判断
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//阈值大小
    }

    /**
     * 构造器:加载因子为0.75默认,有初始容量
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * 构造器:加载因子0.75,初始容量11
     */
    public Hashtable() {
        this(11, 0.75f);
    }

    /**
     * 构造器:有Map映射,构造器初始容量大于映射的两倍
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

    /**
     * 最大容量为int最大值-8
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 动态改变容量大小
     */
    @SuppressWarnings("unchecked")
    protected void rehash() {
        int oldCapacity = table.length;//记录表的老容量
        Entry<?,?>[] oldMap = table;//记录表的数据

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;//判断新的容量与最大值的关系
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)//判断老的容量与最大值的关系
                return;//相等就结束
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;//操作次数增加
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//设置阈值
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {//每一个位置的每一条链
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;//一条链的下一个链接

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;//从新计算引用位置
                e.next = (Entry<K,V>)newMap[index];//将这个与上一个链接
                newMap[index] = e;//赋值
            }
        }
    }

    /**
     * 删除某个词条
     */
    public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];//通过key计算hash值并进一步确定位置
        for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;//将key对应的词条的上和下链接起来
                }
                count--;//数量减1
                V oldValue = e.value;
                e.value = null;//对应处的数值改为Null
                return oldValue;
            }
        }
        return null;
    }

    /**
     * 复制某一Map的所有词条至表中
     */
    public synchronized void putAll(Map<? extends K, ? extends V> t) {
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }


    // Views

    /**
     * 所有的key,entry,values都要加一个锁,保证不发生并发改变的问题
     */
    private transient volatile Set<K> keySet;
    private transient volatile Set<Map.Entry<K,V>> entrySet;
    private transient volatile Collection<V> values;

    /**
     * 
     */
    public Set<K> keySet() {
        if (keySet == null)
            keySet = Collections.synchronizedSet(new KeySet(), this);
        return keySet;
    }

    private class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return getIterator(KEYS);
        }
        public int size() {
            return count;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        public boolean remove(Object o) {
            return Hashtable.this.remove(o) != null;
        }
        public void clear() {
            Hashtable.this.clear();
        }
    }

    /**
     * 
     */
    public Set<Map.Entry<K,V>> entrySet() {
        if (entrySet==null)
            entrySet = Collections.synchronizedSet(new EntrySet(), this);
        return entrySet;
    }

    private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return getIterator(ENTRIES);
        }

        public boolean add(Map.Entry<K,V> o) {
            return super.add(o);
        }

        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
            Object key = entry.getKey();
            Entry<?,?>[] tab = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry<?,?> e = tab[index]; e != null; e = e.next)
                if (e.hash==hash && e.equals(entry))
                    return true;
            return false;
        }

        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
            Object key = entry.getKey();
            Entry<?,?>[] tab = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                if (e.hash==hash && e.equals(entry)) {
                    modCount++;
                    if (prev != null)
                        prev.next = e.next;
                    else
                        tab[index] = e.next;

                    count--;
                    e.value = null;
                    return true;
                }
            }
            return false;
        }

        public int size() {
            return count;
        }

        public void clear() {
            Hashtable.this.clear();
        }
    }

    /**
     * 
     */
    public Collection<V> values() {
        if (values==null)
            values = Collections.synchronizedCollection(new ValueCollection(),
                                                        this);
        return values;
    }

    private class ValueCollection extends AbstractCollection<V> {
        public Iterator<V> iterator() {
            return getIterator(VALUES);
        }
        public int size() {
            return count;
        }
        public boolean contains(Object o) {
            return containsValue(o);
        }
        public void clear() {
            Hashtable.this.clear();
        }
    }




    /**
     * 判等
     */
    public synchronized boolean equals(Object o) {
        if (o == this)//正好相等
            return true;

        if (!(o instanceof Map))//类型不一致
            return false;
        Map<?,?> t = (Map<?,?>) o;
        if (t.size() != size())
            return false;

        try {//判断不相等
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(t.get(key)==null && t.containsKey(key)))//不存在相同key值
                        return false;
                } else {
                    if (!value.equals(t.get(key)))//key对应的位置存在但值不相等
                        return false;
                }
            }
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }

    /**
     * 返回hashcode值
     */
    public synchronized int hashCode() {
        
        int h = 0;
        if (count == 0 || loadFactor < 0)
            return h;  // 空

        loadFactor = -loadFactor;  // 加载因子改为负,作标记,不能被其他进程更改
        Entry<?,?>[] tab = table;
        for (Entry<?,?> entry : tab) {
            while (entry != null) {
                h += entry.hashCode();//hashcode的计算方式:相加该位置所有链接的hash值
                entry = entry.next;
            }
        }

        loadFactor = -loadFactor;  

        return h;
    }

   

   

	/*
	*按照key,value删除
	*/
    @Override
    public synchronized boolean remove(Object key, Object value) {
        Objects.requireNonNull(value);

        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
        for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                e.value = null;
                return true;
            }
        }
        return false;
    }



   

  

    /**
     * 通过流保存文件
     */
    private void writeObject(java.io.ObjectOutputStream s)
            throws IOException {
        Entry<Object, Object> entryStack = null;

        synchronized (this) {
            
            s.defaultWriteObject();

            s.writeInt(table.length);
            s.writeInt(count);

            for (int index = 0; index < table.length; index++) {
                Entry<?,?> entry = table[index];

                while (entry != null) {
                    entryStack =
                        new Entry<>(0, entry.key, entry.value, entryStack);
                    entry = entry.next;
                }
            }
        }

        while (entryStack != null) {
            s.writeObject(entryStack.key);
            s.writeObject(entryStack.value);
            entryStack = entryStack.next;
        }
    }


    /**
     * 词条
     */
    private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;

        protected Entry(int hash, K key, V value, Entry<K,V> next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry<K,V>) next.clone()));
        }

        // Map.Entry Ops

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }
}

数据结构与算法-优先级队列

原文:https://www.cnblogs.com/suit000001/p/13507596.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!