搜索树结构和词典结构，都支持覆盖数据全集的访问和操作。也就是说，其中存储的每一数据对象都可作为查找和访问目标
优先级队列，较之此前的数据结构反而有所削弱。具体地，这类结构将操作对象限定于当前的全局极值者。而维护一个偏序关系
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编码树
}
它是一个完全二叉树，即除了最后一层节点不是满的，其他层节点都是满的，即左右节点都有。
它不是二叉搜索树，即左节点的值都比父节点值小，右节点的值都不比父节点值小，这样查找的时候，就可以通过二分的方式，效率是(log N)。
它是特殊的二叉树，它要求父节点的值不能小于子节点的值。这样保证大的值在上面，小的值在下面。所以堆遍历和查找都是低效的，因为我们只知道从根节点到子叶节点的每条路径都是降序的，但是各个路径之间都是没有联系的，查找一个值时，你不知道应该从左节点查找还是从右节点开始查找。
它可以实现快速的插入和删除，效率都在(log N)左右。所以它可以实现优先级队列。
大顶堆与小顶堆
堆序性也可对称地约定为“堆顶以外的每个节点都不低（小）于其父节点”，此时同理，优先级最低的词条，必然始终处于堆顶位置。为以示区别，通常称前（后）者为大（小）顶堆
模板类与一些常用方法
//必要的方法
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);
}
}
}
原理
实现（还未写）
原理
效率
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