Jump to content
  • Advertisement
  • 09/13/99 06:21 PM
    Sign in to follow this  


    General and Gameplay Programming

    Myopic Rhino
    By viewing the array as a complete binary tree, Heap Sort transforms such a binary tree into a heap. This algorithm does not require overhead and is not recursive. The algorithm basically follows the following steps:
    1. Sort the complete binary tree (actually an array) so that it becomes a max-heap, thus the first element is always the biggest element.
    2. Since what we want is exactly the opposite (the last element should be the biggest instead), we swap the first element and the last element.
    3. Now we have to re-sort the array (except the last element), so that the first element is again the biggest.
    4. Then we repeat the second step, so that the first element is swapped with the current last element.
    5. We repeat 2, 3 so that all the elements are sorted.
    Such a strategy takes the advantage of binary tree. Every time we move an element, we move it to its current position's child. Thus it moves in a greater distance than Insertion Sort.

    Below is the pseudo-code of Heap Sort.

    Heap Sort(Sorting array A[size])

    For each parent node,
    if there is any child node, we compare it with bigger child. If the parent
    is less, we walk down the parent until none of its new children nodes are
    While we do not reach the first cell,
    swap the first cell with the last cell.
    Change the last cell index to the cell preceding the last cell.
    Walk down the first cell until none of its new children nodes are greater.

      Report Article
    Sign in to follow this  

    User Feedback

    There are no comments to display.

    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

  • Advertisement

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!