public class HeapSorted<T>
{
public HeapSorted(IComparer<T> comparer)
{
this.comparer = comparer;
}
IComparer<T> comparer;
List<T> list = new List<T>();
public Int32 Count { get { return list.Count; } }
public void Add(T item)
{
list.Add(item);
Sort();
}
public T this[Int32 index]
{
get
{
return this.list[index: index];
}
set
{
this.list[index: index] = value;
Sort();
}
}
public void RemoveAt(Int32 index)
{
list.RemoveAt(index);
}
public void Sort()
{
// input: an unordered array a of length count
// first place a in max-heap order)
Heapify(list.Count);
Int32 end = list.Count - 1; //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while (end > 0)
{
// (swap the root(maximum value) of the heap with the last element of the heap)
Swap(end, 0);
// (put the heap back in max-heap order)
SiftDown(0, end - 1);
// decrease the size of the heap by one so that the previous max value will
// stay in its proper placement)
end -= 1;
}
}
public void Heapify(Int32 count)
{
// start is assigned the index in a of the last parent node)
Int32 start = (count - 2) / 2;
while (start >= 0)
{
// sift down the node at index start to the proper place such that all nodes below
// the start index are in heap order)
SiftDown(start, count - 1);
start -= 1;
}
// after sifting down the root all nodes/elements are in heap order)
}
public void SiftDown(Int32 start, Int32 end)
{
// input: end represents the limit of how far down the heap
// to sift.
Int32 root = start;
while (root * 2 + 1 <= end)
{
// While the root has at least one child
Int32 child = root * 2 + 1; // root*2+1 points to the left child
// If the child has a sibling and the child's value is less than its sibling's...
if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) < 0)
child += 1; // ... then point to the right child instead
if (comparer.Compare(this.list[root], this.list[child]) < 0)
{
// out of max-heap order
Swap(root, child);
root = child; //repeat to continue sifting down the child now
}
else
return;
}
}
public void Swap(Int32 a, Int32 b)
{
T n = list[a];
list[a] = list;
list = n;
}
}
Critique "my" Heapsort code
Author
In order to speed my A* pathfinding algorithm up, NullSquared suggested using a HeapSort. Since .Net is not kind enough to provide one, I copy-pasta'd off of Wikipedia and ended up with this kludge.
I'm fully aware that it's horrible, feature-wise. What I want right now is two things: Any way to speed it up overall and any way to speed up adding a single item, because it doesn't seem quite right to call the full Sort when adding one item.
Bah. I'm running on far too little sleep after a marathon coding session. Sanity check it or something, please, thanks?
(The A* Pathfinding appears faster)
The code:
Quote:Original post by Narf the Mouse
it doesn't seem quite right to call the full Sort when adding one item.
If you know it is already sorted, then there are more efficient ways of adding it.
Use list.Find() to find the insertion point, then call list.Insert(item).
You could also use a binary search, rather than the linear search done by List.Find().
As I said, use a heap - as in, the data structure. Don't just use heap-sort to sort a list; that is no better than your original usage of quicksort.
As I already recommended, and frob now reiterated, there are more efficient ways than sorting the list.
Quote:Original post by frob
If you know it is already sorted, then there are more efficient ways of adding it.
Use list.Find() to find the insertion point, then call list.Insert(item).
You could also use a binary search, rather than the linear search done by List.Find().
As I already recommended, and frob now reiterated, there are more efficient ways than sorting the list.
Author
Plan for tomorrow: Turn it into an actual heap. I should be able to do that, once my think can brain.
Quote:Original post by Narf the Mouse
Plan for tomorrow: Turn it into an actual heap. I should be able to do that, once my think can brain.
If you are looking to turn it into an actual heap (rather than a heapsort, which is different), then yes, you will need to heap-ify it after every insertion. That's necessary to ensure that items bubble up or down as necessary.
Author
After the nap...
Ok, something seems wrong with one of these two functions:
To wit, my A* pathfinding that I'm using it for doesn't fully optimize; it'll take weird jags into alcoves. The only changes I've made to it are to use HeapSorted.
Ok, something seems wrong with one of these two functions:
To wit, my A* pathfinding that I'm using it for doesn't fully optimize; it'll take weird jags into alcoves. The only changes I've made to it are to use HeapSorted.
public void Add(T item) { Int32 child = 0; Int32 end = this.list.Count - 1; while (child * 2 + 1 < end && comparer.Compare(item, this.list[child * 2 + 1]) < 0) { child = child * 2 + 1; if (child < end && comparer.Compare(item, this.list[child + 1]) < 0) child += 1; } list.Insert(child, item); Heapify(); } public T RemoveLowest() { Int32 child = 0; Int32 end = this.list.Count - 1; while (child * 2 + 1 < end) { child = child * 2 + 1; if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) >= 0) child += 1; } // This is faster than RemoveAt in the middle of the list. // Removing at the end, it just --'s the List.Count. T temp = this.list[child]; this.list[child] = this.list[end]; this.list.RemoveAt(end); Heapify(); return temp; }
Author
The problem seems to be that Heapify only gaurentees that the lowest values will be at the bottom of the tree, not that the lowest values will be systematically findable.
Author
...And then, in the middle of something else, I realized that I should probably be using a MinHeap...
Author
So now it can do MaxHeap and MinHeap. SiftUp should be SiftDownMin, but meh, it's time and past time I should be sleeping.
public class HeapSorted<T> { public HeapSorted(IComparer<T> comparer, Boolean maxHeap = true) { this.comparer = comparer; } IComparer<T> comparer; protected Boolean maxHeap; List<T> list = new List<T>(); public Int32 Count { get { return list.Count; } } public void Add(T item) { list.Add(item); Heapify(); } public T this[Int32 index] { get { return this.list[index: index]; } set { this.list[index: index] = value; Sort(); } } public T RemoveLowest() { Int32 end = this.list.Count - 1; T temp = this.list[0]; this.list[0] = this.list[end]; this.list.RemoveAt(end); Heapify(); return temp; } public void Sort() { // input: an unordered array a of length count // first place a in max-heap order) Heapify(); Int32 end = list.Count - 1; //in languages with zero-based arrays the children are 2*i+1 and 2*i+2 while (end > 0) { // (swap the root(maximum value) of the heap with the last element of the heap) Swap(end, 0); // (put the heap back in max-heap order) SiftDown(0, end - 1); // decrease the size of the heap by one so that the previous max value will // stay in its proper placement) end -= 1; } } public void Heapify() { Int32 count = this.list.Count; if (maxHeap) { // start is assigned the index in a of the last parent node) Int32 start = (count - 2) / 2; while (start >= 0) { // sift down the node at index start to the proper place such that all nodes below // the start index are in heap order) SiftDown(start, count - 1); start -= 1; } // after sifting down the root all nodes/elements are in heap order) } else { // start is assigned the index in a of the last parent node) Int32 start = (count - 2) / 2; while (start >= 0) { // sift down the node at index start to the proper place such that all nodes below // the start index are in heap order) SiftUp(start, count - 1); start -= 1; } // after sifting down the root all nodes/elements are in heap order) } } public void SiftDown(Int32 start, Int32 end) { // input: end represents the limit of how far down the heap // to sift. Int32 root = start; while (root * 2 + 1 <= end) { // While the root has at least one child Int32 child = root * 2 + 1; // root*2+1 points to the left child // If the child has a sibling and the child's value is less than its sibling's... if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) < 0) child += 1; // ... then point to the right child instead if (comparer.Compare(this.list[root], this.list[child]) < 0) { // out of max-heap order Swap(root, child); root = child; //repeat to continue sifting down the child now } else return; } } public void SiftUp(Int32 start, Int32 end) { // input: end represents the limit of how far down the heap // to sift. Int32 root = start; while (root * 2 + 1 <= end) { // While the root has at least one child Int32 child = root * 2 + 1; // root*2+1 points to the left child // If the child has a sibling and the child's value is less than its sibling's... if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) > 0) child += 1; // ... then point to the right child instead if (comparer.Compare(this.list[root], this.list[child]) > 0) { // out of max-heap order Swap(root, child); root = child; //repeat to continue sifting down the child now } else return; } } public void Swap(Int32 a, Int32 b) { T n = list[a]; list[a] = list; list = n; } }
Author
I suspect it's not a proper binary heap, or the GetNext would always return the proper next value. This is a preliminary post; I'm going to look into that.
In the meantime, here's the current code:
In the meantime, here's the current code:
public class SortedHeap<T> { public SortedHeap(IComparer<T> comparer, Boolean maxHeap = true) { this.comparer = comparer; } IComparer<T> comparer; protected Boolean maxHeap; List<T> list = new List<T>(); public Int32 Count { get { return list.Count; } } public void Add(T item) { list.Add(item); // Heapify(); if (this.maxHeap) this.SiftMax(0, this.list.Count - 1); else this.SiftMin(0, this.list.Count - 1); } public T this[Int32 index] { get { return this.list[index: index]; } set { this.list[index: index] = value; Sort(); } } public T GetNext() { Int32 end = this.list.Count - 1; T temp = this.list[0]; this.list[0] = this.list[end]; this.list.RemoveAt(end); // Heapify(); /* if (this.maxHeap) this.SiftDown(0, this.list.Count - 1); else this.SiftUp(0, this.list.Count - 1); */ if (this.maxHeap) this.MaxHeapify(0); else this.MinHeapify(0); return temp; } public void Sort() { // input: an unordered array a of length count // first place a in max-heap order) Heapify(); Int32 end = list.Count - 1; //in languages with zero-based arrays the children are 2*i+1 and 2*i+2 while (end > 0) { // (swap the root(maximum value) of the heap with the last element of the heap) Swap(end, 0); // (put the heap back in max-heap order) SiftMax(0, end - 1); // decrease the size of the heap by one so that the previous max value will // stay in its proper placement) end -= 1; } } public void MaxHeapify(Int32 i) { Int32 left = 2 * i + 1; Int32 right = 2 * i + 2; Int32 largest; if (left <= this.list.Count && comparer.Compare(this.list, this.list) > 0) largest = left; else largest = i; if (right <= this.list.Count && comparer.Compare(this.list, this.list[largest]) > 0) largest = right; if (largest != i) { Swap(i, largest); MaxHeapify(largest); } } public void MinHeapify(Int32 i) { Int32 left = 2 * i + 1; Int32 right = 2 * i + 2; Int32 smallest; if (left < this.list.Count && comparer.Compare(this.list, this.list) < 0) smallest = left; else smallest = i; if (right < this.list.Count && comparer.Compare(this.list, this.list[smallest]) < 0) smallest = right; if (smallest != i) { Swap(i, smallest); MinHeapify(smallest); } } public void Heapify() { Int32 count = this.list.Count; if (maxHeap) { // start is assigned the index in a of the last parent node) Int32 start = (count - 2) / 2; while (start >= 0) { // sift down the node at index start to the proper place such that all nodes below // the start index are in heap order) SiftMax(start, count - 1); start -= 1; } // after sifting down the root all nodes/elements are in heap order) } else { // start is assigned the index in a of the last parent node) Int32 start = (count - 2) / 2; while (start >= 0) { // sift down the node at index start to the proper place such that all nodes below // the start index are in heap order) SiftMin(start, count - 1); start -= 1; } // after sifting down the root all nodes/elements are in heap order) } } public void SiftMax(Int32 start, Int32 end) { // input: end represents the limit of how far down the heap // to sift. Int32 root = start; while (root * 2 + 1 <= end) { // While the root has at least one child Int32 child = root * 2 + 1; // root*2+1 points to the left child // If the child has a sibling and the child's value is less than its sibling's... if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) < 0) child += 1; // ... then point to the right child instead if (comparer.Compare(this.list[root], this.list[child]) < 0) { // out of max-heap order Swap(root, child); root = child; //repeat to continue sifting down the child now } else return; } } public void SiftMin(Int32 start, Int32 end) { // input: end represents the limit of how far down the heap // to sift. Int32 root = start; while (root * 2 + 1 <= end) { // While the root has at least one child Int32 child = root * 2 + 1; // root*2+1 points to the left child // If the child has a sibling and the child's value is less than its sibling's... if (child < end && comparer.Compare(this.list[child], this.list[child + 1]) > 0) child += 1; // ... then point to the right child instead if (comparer.Compare(this.list[root], this.list[child]) > 0) { // out of max-heap order Swap(root, child); root = child; //repeat to continue sifting down the child now } else return; } } public void Swap(Int32 a, Int32 b) { T n = list[a]; list[a] = list; list = n; } }This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
