Danny.HeapSort
From Apache OpenOffice Wiki
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