122 lines
4.4 KiB
C#
122 lines
4.4 KiB
C#
namespace PriorityQ {
|
|
using KeyT = UInt32;
|
|
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
class Tuple<K, V> { // for DotNet 3.5 without Tuple's
|
|
public K Item1; public V Item2;
|
|
public Tuple(K k, V v) { Item1 = k; Item2 = v; }
|
|
public override string ToString() {
|
|
return "(" + Item1.ToString() + ", " + Item2.ToString() + ")";
|
|
}
|
|
}
|
|
class MinHeapPQ<V> {
|
|
private struct HeapEntry {
|
|
public KeyT k; public V v;
|
|
public HeapEntry(KeyT k, V v) { this.k = k; this.v = v; }
|
|
}
|
|
private List<HeapEntry> pq;
|
|
private MinHeapPQ() { this.pq = new List<HeapEntry>(); }
|
|
private bool mt { get { return pq.Count == 0; } }
|
|
private int sz {
|
|
get {
|
|
var cnt = pq.Count;
|
|
return (cnt == 0) ? 0 : cnt - 1;
|
|
}
|
|
}
|
|
private Tuple<KeyT, V> pkmn {
|
|
get {
|
|
if (pq.Count == 0) return null;
|
|
else {
|
|
var mn = pq[0];
|
|
return new Tuple<KeyT, V>(mn.k, mn.v);
|
|
}
|
|
}
|
|
}
|
|
private void psh(KeyT k, V v) { // add extra very high item if none
|
|
if (pq.Count == 0) pq.Add(new HeapEntry(UInt32.MaxValue, v));
|
|
var i = pq.Count; pq.Add(pq[i - 1]); // copy bottom item...
|
|
for (var ni = i >> 1; ni > 0; i >>= 1, ni >>= 1) {
|
|
var t = pq[ni - 1];
|
|
if (t.k > k) pq[i - 1] = t; else break;
|
|
}
|
|
pq[i - 1] = new HeapEntry(k, v);
|
|
}
|
|
private void siftdown(KeyT k, V v, int ndx) {
|
|
var cnt = pq.Count - 1; var i = ndx;
|
|
for (var ni = i + i + 1; ni < cnt; ni = ni + ni + 1) {
|
|
var oi = i; var lk = pq[ni].k; var rk = pq[ni + 1].k;
|
|
var nk = k;
|
|
if (k > lk) { i = ni; nk = lk; }
|
|
if (nk > rk) { ni += 1; i = ni; }
|
|
if (i != oi) pq[oi] = pq[i]; else break;
|
|
}
|
|
pq[i] = new HeapEntry(k, v);
|
|
}
|
|
private void rplcmin(KeyT k, V v) {
|
|
if (pq.Count > 1) siftdown(k, v, 0);
|
|
}
|
|
private void dltmin() {
|
|
var lsti = pq.Count - 2;
|
|
if (lsti <= 0) pq.Clear();
|
|
else {
|
|
var lkv = pq[lsti];
|
|
pq.RemoveAt(lsti); siftdown(lkv.k, lkv.v, 0);
|
|
}
|
|
}
|
|
private void reheap(int i) {
|
|
var lfti = i + i + 1;
|
|
if (lfti < sz) {
|
|
var rghti = lfti + 1; reheap(lfti); reheap(rghti);
|
|
var ckv = pq[i]; siftdown(ckv.k, ckv.v, i);
|
|
}
|
|
}
|
|
private void bld(IEnumerable<Tuple<KeyT, V>> sq) {
|
|
var sqm = from e in sq
|
|
select new HeapEntry(e.Item1, e.Item2);
|
|
pq = sqm.ToList<HeapEntry>();
|
|
var sz = pq.Count;
|
|
if (sz > 0) {
|
|
var lkv = pq[sz - 1];
|
|
pq.Add(new HeapEntry(KeyT.MaxValue, lkv.v));
|
|
reheap(0);
|
|
}
|
|
}
|
|
private IEnumerable<Tuple<KeyT, V>> sq() {
|
|
return from e in pq
|
|
where e.k != KeyT.MaxValue
|
|
select new Tuple<KeyT, V>(e.k, e.v); }
|
|
private void adj(Func<KeyT, V, Tuple<KeyT, V>> f) {
|
|
var cnt = pq.Count - 1;
|
|
for (var i = 0; i < cnt; ++i) {
|
|
var e = pq[i];
|
|
var r = f(e.k, e.v);
|
|
pq[i] = new HeapEntry(r.Item1, r.Item2);
|
|
}
|
|
reheap(0);
|
|
}
|
|
public static MinHeapPQ<V> empty { get { return new MinHeapPQ<V>(); } }
|
|
public static bool isEmpty(MinHeapPQ<V> pq) { return pq.mt; }
|
|
public static int size(MinHeapPQ<V> pq) { return pq.sz; }
|
|
public static Tuple<KeyT, V> peekMin(MinHeapPQ<V> pq) { return pq.pkmn; }
|
|
public static MinHeapPQ<V> push(KeyT k, V v, MinHeapPQ<V> pq) {
|
|
pq.psh(k, v); return pq; }
|
|
public static MinHeapPQ<V> replaceMin(KeyT k, V v, MinHeapPQ<V> pq) {
|
|
pq.rplcmin(k, v); return pq; }
|
|
public static MinHeapPQ<V> deleteMin(MinHeapPQ<V> pq) { pq.dltmin(); return pq; }
|
|
public static MinHeapPQ<V> merge(MinHeapPQ<V> pq1, MinHeapPQ<V> pq2) {
|
|
return fromSeq(pq1.sq().Concat(pq2.sq())); }
|
|
public static MinHeapPQ<V> adjust(Func<KeyT, V, Tuple<KeyT, V>> f, MinHeapPQ<V> pq) {
|
|
pq.adj(f); return pq; }
|
|
public static MinHeapPQ<V> fromSeq(IEnumerable<Tuple<KeyT, V>> sq) {
|
|
var pq = new MinHeapPQ<V>(); pq.bld(sq); return pq; }
|
|
public static Tuple<Tuple<KeyT, V>, MinHeapPQ<V>> popMin(MinHeapPQ<V> pq) {
|
|
var rslt = pq.pkmn; if (rslt == null) return null;
|
|
pq.dltmin(); return new Tuple<Tuple<KeyT, V>, MinHeapPQ<V>>(rslt, pq); }
|
|
public static IEnumerable<Tuple<KeyT, V>> toSeq(MinHeapPQ<V> pq) {
|
|
for (; !pq.mt; pq.dltmin()) yield return pq.pkmn; }
|
|
public static IEnumerable<Tuple<KeyT, V>> sort(IEnumerable<Tuple<KeyT, V>> sq) {
|
|
return toSeq(fromSeq(sq)); }
|
|
}
|
|
}
|