Topic Text   Topic Comments (1)   Topic Properties   Topic Information alecito13@hot...
Topic title: k lo k Tuesday April 2, 2013 13:20:37

Download topic text | View in variable-width font | Tab width set to 4 (change to 8)

Files in topic: (view all files)  
heap_sort.py   {+63,-0}

[Add General Comment] to topic.

File heap_sort.py (Revision 1.0) [Add File Comment] [Top]
 
1 def PARENT(heap, index):
2 return int(index/2)
3
4 def CHILD_LEFT(heap, index):
5 return index * 2 + 1
6
7 def CHILD_RIGHT(heap, index):
8 return index * 2 + 2
9
10 def MAX_HEAPFY(heap, index):
11 heap_len = len(heap)
12
13 #if the index is not in the heap, return Null
14 if heap_len <= index:
15 return heap
16
17 #grab childs
18 left_i = CHILD_LEFT(heap,index)
19 right_i = CHILD_RIGHT(heap,index)
20 max_i = None
21 #If the left child exists for this node
22 if heap_len > left_i:
23 #print("Hola2")
24 #grab its value and set the max_val to it
25 max_i = left_i
26 #Do the same for the right child and grab the max
27 if heap_len > right_i and heap[right_i] > heap[max_i]:
28 max_i = right_i
29 if max_i == None:
30 return heap
31 if heap[index] < heap[max_i]:
32 temp = heap[index]
33 heap[index] = heap[max_i]
34 heap[max_i] = temp
35 return MAX_HEAPFY(heap, max_i)
36 return heap
37
38 def BUILD_HEAP(array):
39 array_len = int(len(array)/2)
40 heap = array;
41 for i in reversed(range(array_len)):
42 MAX_HEAPFY(heap, i)
43 return heap;
44
45 def HEAP_SORT(heap):
46 sorted_heap = []
47 while(True):
48 heap_len = len(heap)
49 if(heap_len == 0):
50 break
51 temp = heap[0]
52 heap[0] = heap[heap_len-1]
53 heap[heap_len - 1] = temp
54 sorted_heap.append(heap.pop(-1))
55 heap = MAX_HEAPFY(heap,0)
56 print(heap)
57 return sorted_heap
58
59 x = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
60
61 print(x)
62 print(BUILD_HEAP(x))
63 print(HEAP_SORT(x))
 
File heap_sort.py (Revision 1.0) [Add File Comment] [Top]
  
Legend:
Removed 
Changed
 Added

[Add General Comment] to topic.