[已解决]树形选择排序问题

tinytsa86

利用树形选择排序（锦标赛排序）从8个队中选出最大者冠军，亚军，季军，最多需要比赛多少场？
希望回答者能给出答案和解题思路过程。谢谢啦！

最佳答案

月排行榜 / 总排行榜

不二如是

2015-11-19 19:50:01

推荐：https://fishc.com.cn/thread-211114-1-1.html

1. def heapBasic(heap,heaplen,i):
   
2.     left = 2*i + 1
   
3.     right = 2*i + 2
   
4.     larger = i
   
5.     if left < heaplen and heap[larger] < heap[left]:
   
6.         larger = left
   
7.     if right < heaplen and heap[larger] < heap[right]:
   
8.         larger = right
   
9.     if larger != i:
   
10.         heap[larger], heap[i] = heap[i], heap[larger]
    
11.         heapBasic(heap, heaplen, larger)
    
12.          
    
13. def buildHeap(heap):
    
14.     heap_len = len(heap)
    
15.     for i in range((heap_len -2)//2,-1,-1):
    
16.         heapBasic(heap, heap_len, i)
    
17.         
    
18. def heapSort(heap):
    
19.     buildHeap(heap)
    
20.     for i in range(len(heap)-1, -1, -1):
    
21.         heap[0], heap[i] = heap[i], heap[0]
    
22.         heapBasic(heap, i, 0)
    
23. 
    
24. data = [99,66,88,55,3,23]
    
25. print("原始数据：")
    
26. for k in range(len(data)):
    
27.     print(f"{data[k]}",end=' ')
    
28. print('\n----我是分界线------\n')
    
29. print("堆排序后结果：")
    
30. heapSort(data)
    
31. for k in range(len(data)):
    
32.           print(f"{data[k]}",end=' ')   

复制代码

跳转到最佳答案楼层

不二如是

推荐：https://fishc.com.cn/thread-211114-1-1.html

1. def heapBasic(heap,heaplen,i):
   
2.     left = 2*i + 1
   
3.     right = 2*i + 2
   
4.     larger = i
   
5.     if left < heaplen and heap[larger] < heap[left]:
   
6.         larger = left
   
7.     if right < heaplen and heap[larger] < heap[right]:
   
8.         larger = right
   
9.     if larger != i:
   
10.         heap[larger], heap[i] = heap[i], heap[larger]
    
11.         heapBasic(heap, heaplen, larger)
    
12.          
    
13. def buildHeap(heap):
    
14.     heap_len = len(heap)
    
15.     for i in range((heap_len -2)//2,-1,-1):
    
16.         heapBasic(heap, heap_len, i)
    
17.         
    
18. def heapSort(heap):
    
19.     buildHeap(heap)
    
20.     for i in range(len(heap)-1, -1, -1):
    
21.         heap[0], heap[i] = heap[i], heap[0]
    
22.         heapBasic(heap, i, 0)
    
23. 
    
24. data = [99,66,88,55,3,23]
    
25. print("原始数据：")
    
26. for k in range(len(data)):
    
27.     print(f"{data[k]}",end=' ')
    
28. print('\n----我是分界线------\n')
    
29. print("堆排序后结果：")
    
30. heapSort(data)
    
31. for k in range(len(data)):
    
32.           print(f"{data[k]}",end=' ')   

复制代码

ExiaGN001

首先，8队二分，比出第一，需要7场
其次，第二只可能被第一击败，在第一击败的3个队伍中比赛2场，求出第二
再次，第三只能被第一或第二击败，在第一击败的2队(去掉第二)和第二击败的2队（没打败第一）中再二分求出第三，需要3场
7+2+3=12场
如果有用，麻烦设置最佳答案，谢谢~