Danny.HeapSort

Here is my HeapSort module. This is NOT an OOo related module, but I am posting it because someone asked.....

#********************************************************************** 
# 
#   Danny.HeapSort.py 
# 
#********************************************************************** 
#   Copyright (c) 2005 Danny Brewer 
#   d29583@groovegarden.com 
# 
#   This library is free software; you can redistribute it and/or 
#   modify it under the terms of the GNU Lesser General Public 
#   License as published by the Free Software Foundation; either 
#   version 2.1 of the License, or (at your option) any later version. 
# 
#   This library is distributed in the hope that it will be useful, 
#   but WITHOUT ANY WARRANTY; without even the implied warranty of 
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
#   Lesser General Public License for more details. 
# 
#   You should have received a copy of the GNU Lesser General Public 
#   License along with this library; if not, write to the Free Software 
#   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
# 
#   See:  http://www.gnu.org/licenses/lgpl.html 
# 
#********************************************************************** 
#   If you make changes, please append to the change log below. 
# 
#   Change Log 
#   Danny Brewer         Revised 2005-03-29 
# 
#********************************************************************** 


def SwapItems( items, nIndex1, nIndex2 ): 
    """Swap two items in the sequence.  Return a new sequence with the swap. 
    nIndex1 and nIndex2 are zero based.""" 
    item1 = items[nIndex1] 
    item2 = items[nIndex2] 
    items[nIndex1] = item2 
    items[nIndex2] = item1 
    return items 

def ItemsCompareGreater( items, nIndex1, nIndex2 ): 
    """Return True if the item at nIndex1 is greater than the item at nIndex2. 
    nIndex1 and nIndex2 are zero based.""" 
    return items[nIndex1] > items[nIndex2] 



def HeapSort( items, 
                      compareGreaterProc=ItemsCompareGreater, 
                      swapProc=SwapItems ): 
    MakeHeap( items, compareGreaterProc, swapProc ) 
    nNumItems = len( items ) 
    for i in range( nNumItems-1, -1, -1 ): 
        swapProc( items, 0, i ) 
        SiftHeap( items, i, 0, compareGreaterProc, swapProc ) 
    return items 


def MakeHeap( items, 
                      compareGreaterProc=ItemsCompareGreater, 
                      swapProc=SwapItems ): 
    nNumItems = len( items ) 
    for i in range( nNumItems-1, -1, -1 ): 
        SiftHeap( items, nNumItems, i, compareGreaterProc, swapProc ) 


def SiftHeap( items, nHeapSize, nTheNode, 
                      compareGreaterProc=ItemsCompareGreater, 
                      swapProc=SwapItems ): 
    nLargestNode = nTheNode 
    while True: 
        bNeedSwap = False 
        nParentNode = nLargestNode 

        nChildNode = nParentNode+nParentNode+1 # left child 
        if( nChildNode < nHeapSize and compareGreaterProc( items, nChildNode, nLargestNode ) ): 
            nLargestNode = nChildNode 
            bNeedSwap = True 

        nChildNode = nChildNode + 1 # right child 
        if( nChildNode < nHeapSize and compareGreaterProc( items, nChildNode, nLargestNode ) ): 
            nLargestNode = nChildNode 
            bNeedSwap = True 

        if bNeedSwap: 
            swapProc( items, nParentNode, nLargestNode ) 
        else: 
            break