Sign in to follow this  
Narf the Mouse

Critique "my" Heapsort code

Recommended Posts

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:
    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[b];
            list[b] = n;
        }
    }

Share this post


Link to post
Share on other sites
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().

Share this post


Link to post
Share on other sites
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.

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


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;
}


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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[b];
list[b] = n;
}
}

Share this post


Link to post
Share on other sites
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:

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[left], this.list[i]) > 0)
largest = left;
else
largest = i;
if (right <= this.list.Count && comparer.Compare(this.list[right], 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[left], this.list[i]) < 0)
smallest = left;
else
smallest = i;
if (right < this.list.Count && comparer.Compare(this.list[right], 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[b];
list[b] = n;
}
}

Share this post


Link to post
Share on other sites
Thanks for your help. :)

And, after some research - It's a perfectly proper binary heap; it's just not an *organized* binary tree. While Heapify guarantees that the proper value will always be at the top, nothing guarantees any certain order to where the values are stored.

An AA Binary Tree looked like it provided that guarantee, so I made one of those.

Working on getting and removing the lowest value as well as enumeration. Due to events, my brain is not in top shape, but anyway...

[Serializable]
public class BinaryTree2<T> /* : IEnumerable<T> */
{
public BinaryTree2(IComparer<T> comparer)
{
this.rawValues = new List<T>();
this.organizer = new List<Leaf>();
this.comparer = comparer;
temp = new Leaf();
}


protected List<T> rawValues;
protected List<Leaf> organizer;
protected IComparer<T> comparer;
Int32 root;


public void Add(T value)
{
rawValues.Add(value);
if (organizer.Count > 0)
{
root = Insert(rawValues.Count - 1, 0);
}
else
{
organizer.Add(new Leaf(rawValues.Count - 1, 1));
root = organizer.Count - 1;
}
}


/* public T PopLowest()
{
if (root != null)
{
Leaf node = null;
if (root.Left != null)
node = root.LeftMost;
else if (root.Right != null)
node = root.Right.LeftMost;
T value = node.Value;
root = this.Delete(node.Value, ref root);
return value;
}
throw new NullReferenceException("No data avialable.");
} */



Leaf temp;
public Int32 Insert(Int32 valueLocation, Int32 node)
{
// input: X, the value to be inserted, and T, the root of the tree to insert it into.
// output: A balanced version T including X.


// Do the normal binary tree insertion procedure. Set the result of the
// recursive call to the correct child in case a new node was created or the
// root of the subtree changes.
if (node == -1)
// Create a new leaf node with X.
{
organizer.Add(new Leaf(valueLocation, 1));
return organizer.Count - 1;
}

else if (comparer.Compare(rawValues[valueLocation], rawValues[organizer[node].myself]) <= 0)
{
temp = organizer[node];
temp.Left = Insert(valueLocation, organizer[node].Left);
organizer[node] = temp;
}
else if (comparer.Compare(rawValues[valueLocation], rawValues[organizer[node].myself]) > 0)
{
temp = organizer[node];
temp.Right = Insert(valueLocation, organizer[node].Right);
organizer[node] = temp;
}
// Note that the case of X == value(T) is unspecified. As given, an insert
// will have no effect. The implementor may desire different behavior.

// Perform skew and then split. The conditionals that determine whether or
// not a rotation will occur or not are inside of the procedures, as given
// above.
node = Skew(ref node);
node = Split(ref node);

return node;
}


/* public Leaf Delete(T value, ref Leaf node)
{
// input: X, the value to delete, and T, the root of the tree from which it should be deleted.
// output: T, balanced, without the value X.
if (comparer.Compare(value, node.Value) > 0 && node.Right != null)
node.Right = Delete(value, ref node.Right);
else if (comparer.Compare(value, node.Value) < 0 && node.Left != null)
node.Left = Delete(value, ref node.Left);
else
{
// If we're a leaf, easy, otherwise reduce to leaf case.
if (node.End)
return null;
else if (node.Left == null)
{
T L = node.Successor.Value;
node.Right = Delete(L, ref node.Right);
node.Value = L;
}
else
{
T L = node.Predecessor.Value;
node.Left = Delete(L, ref node.Left);
node.Value = L;
}
}

// Rebalance the tree. Decrease the level of all nodes in this level if
// necessary, and then skew and split all nodes in the new level.
node = DecreaseLevel(ref node);
node = Skew(ref node);
if (node.Right != null)
{
node.Right = Skew(ref node.Right);
// right(right(T)) := skew(right(right(T)))
if (node.Right.Right != null)
node.Right.Right = Skew(ref node.Right.Right);
}
node = Split(ref node);
if (node.Right != null)
node.Right = Split(ref node.Right);
return node;
}


public Leaf DecreaseLevel(ref Leaf node)
{
// input: T, a tree for which we want to remove links that skip levels.
// output: T with its level decreased.
if (node.Left != null && node.Right != null)
{
Int32 should_be = Math.Min(node.Left.Level, node.Right.Level) + 1;
if (should_be < node.Level)
{
node.Level = should_be;
if (should_be < node.Right.Level)
node.Right.Level = should_be;
}
}
return node;
} */



public Int32 Skew(ref Int32 node)
{
// input: T, a node representing an AA tree that needs to be rebalanced.
// output: Another node representing the rebalanced AA tree.

if (node == -1)
return -1;
else if (organizer[node].Left != -1
&& organizer[organizer[node].Left].Level == organizer[node].Level)
{
// Swap the pointers of horizontal left links.
Int32 L = organizer[node].Left;
temp = organizer[node];
temp.Left = organizer[L].Right;
organizer[node] = temp;
temp = organizer[L];
temp.Right = node;
organizer[L] = temp;
return L;
}
else
return node;
}


public Int32 Split(ref Int32 node)
{
// input: T, a node representing an AA tree that needs to be rebalanced.
// output: Another node representing the rebalanced AA tree.

if (node == -1)
return -1;
else if (organizer[node].Right != -1
&& organizer[organizer[node].Right].Right != -1
&& organizer[node].Level == organizer[organizer[organizer[node].Right].Right].Level)
{
// We have two horizontal right links. Take the middle node, elevate it, and return it.
Int32 R = organizer[node].Right;
temp = organizer[node];
temp.Right = organizer[R].Left;
organizer[node] = temp;
temp = organizer[R];
temp.Left = node;
temp.Level += 1;
organizer[R] = temp;
return R;
}
else
return node;
}


public struct Leaf
{
public Leaf(Int32 self, Int32 level)
{
this.myself = self;
this.Level = level;
this.Left = -1;
this.Right = -1;
}

#region Body

public Int32 Level;
public Int32 myself;
public Int32 Left;
public Int32 Right;
public Boolean End { get { return this.Left == -1 || this.Right == -1; } }

#endregion


/* public override string ToString()
{
return "V: " + Value;
} */

}


public void Traverse(Action<T> callback)
{
// this.root.Traverse(callback);
this.TraverseInner(callback, root);
}


protected void TraverseInner(Action<T> callback, Int32 node)
{
if (organizer[node].Left != -1)
TraverseInner(callback, organizer[node].Left);
callback(rawValues[organizer[node].myself]);
if (organizer[node].Right != -1)
TraverseInner(callback, organizer[node].Right);
}


/* public struct BinaryTreeEnumerator : IEnumerator<T>
{
public BinaryTreeEnumerator(BinaryTree<T> tree)
{
this.tree = tree;
node = tree.root;
max = default(T);
started = false;
}


private BinaryTree<T> tree;
private Leaf node;
private T max;
private Boolean started;


public T Current
{
get { return node.Value; }
}

public void Dispose()
{
tree = null;
node = null;
}

object System.Collections.IEnumerator.Current
{
get { return node.Value; }
}

public bool MoveNext()
{
node = tree.root;
Boolean found = MoveNextInner();


return found;
}


private Boolean MoveNextInner()
{
Boolean found = false;
if (node.Left != null
&& (!started || tree.comparer.Compare(node.Left.Value, max) > 0))
{
node = node.Left;
found = MoveNextInner();
}
if (!started)
{
max = node.Value;
started = true;
found = true;
}
else if (tree.comparer.Compare(node.Value, max) > 0)
{
max = node.Value;
found = true;
}
if (node.Right != null
&& (!started || tree.comparer.Compare(node.Right.Value, max) > 0) && !found)
{
node = node.Right;
found = MoveNextInner();
}
if (tree.comparer.Compare(node.Value, max) > 0)
{
max = node.Value;
found = true;
}
return found;
}

public void Reset()
{
node = tree.root;
}
}



public IEnumerator<T> GetEnumerator()
{
return new BinaryTree<T>.BinaryTreeEnumerator(this);
}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return new BinaryTree<T>.BinaryTreeEnumerator(this);
} */

}


Share this post


Link to post
Share on other sites
Quote:
Original post by Narf the Mouse
And, after some research - It's a perfectly proper binary heap; it's just not an *organized* binary tree. While Heapify guarantees that the proper value will always be at the top, nothing guarantees any certain order to where the values are stored.


Because you don't need that guarantee for heapsort, and it just adds extra work in normal cases. You just iteratively pull off the top element, and the results are necessarily sorted - because the first element you pulled off was the biggest (or smallest, or most X-quality) of all of them, and then the next was the biggest of all the rest, i.e. the second-biggest of all of them, etc.

Of course, if you do actually need that guarantee for something else, then go ahead and enforce it.

Share this post


Link to post
Share on other sites
The thing is, Heapify is not O log N. So, I'm making a second class which is an organized binary tree which would be O log N - For the sole purpose of seeing how it affects the speed.

Edit: It would very likely be slower for small numbers of items, but may speed up large maps. Possibly, I could write something to switch between them.

You can see the code for it above.

[Edited by - Narf the Mouse on April 6, 2010 7:06:57 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this