Jump to content
  • Advertisement
Sign in to follow this  
Narf the Mouse

Critique "my" Heapsort code

This topic is 3025 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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;
            list = n;
        }
    }

Share this post


Link to post
Share on other sites
Advertisement
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;
list = 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

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!