5 篇笔记 写笔记

1. #0

   heuwst

   674***[email protected]

   13

   改进参考代码:

   1、迭代堆化

   2、迭代的两种写法

   def heapify(arr):
    n = len(arr)
    for i in reversed(range(n // 2)):
    shiftDown(arr,n,i)
   def shiftDown(arr, n, k):
    while 2 * k + 1 < n:
    j = 2 * k + 1
    if j + 1 < n and arr[j + 1] < arr[j]:
    j += 1
    if arr[k] <= arr[j]:
    break
    arr[k], arr[j] = arr[j], arr[k]
    k = j
   def shiftDown2(arr, n, k):
    smallest, l, r = k, 2 * k + 1, 2 * k + 2
    while l < n:
    if arr[l] < arr[smallest]:
    smallest = l
    if r < n and arr[r] < arr[smallest]:
    smallest = r
    if smallest == k:
    break
    else:
    arr[k], arr[smallest] = arr[smallest], arr[k]
    k = smallest
    l, r = 2 * k + 1, 2 * k + 2
   def heapSort(arr):
    n=len(arr)
    heapify(arr)
    print("堆化:",arr)
    for i in range(n-1):
    arr[n-i-1],arr[0] = arr[0],arr[n-i-1]
    # print("交换最小值后:",arr)
    shiftDown(arr,n-i-1,0)
    # print("调整后:",arr)
   arr = [3,2,1,9,7,8]
   heapSort(arr)
   print("排序后:",arr)
   

   heuwst

   674***[email protected]

   7年前 (2020年01月28日)
2. #0

   小白

   673***[email protected]

   1

   堆排序有点像先二分法找极大值,再冒泡排序:

   # 假定数组最后一位是根节点,其他部分平分为分支节点
   # 经过一次OneHeapSort,找到最大值并放到根节点
   def OneHeapSort(list, l, r):
    if r-l<=0:
    return
    if r-l==1 and list[l]>list[r]:
    list[l],list[r] = list[r],list[l]
    else:
    middle = l + (r-l-1)//2
    OneHeapSort(list, l, middle)
    OneHeapSort(list, middle+1, r-1)
    if list[middle]>list[r]:
    list[middle],list[r] = list[r],list[middle]
    if list[r-1]>list[r]:
    list[r-1],list[r] = list[r],list[r-1]
   # 依次将最大值放到数组的后面
   def heapSort(list):
    for i in range(len(list)-1, 0, -1):
    OneHeapSort(list, 0, i)
   list = [1, 10, 8, 200, 50, 4]
   heapSort(list)
   print(list) # [1,4,8,10,50,200]

   小白

   673***[email protected]

   6年前 (2020年03月24日)
3. #0

   noname

   ZHK***[email protected]

   4

   上面那个就不算堆排序,感觉是强行弄个什么根节点出来,稍微改下有点像归并排序,只不过归并排序是给子序列排序,而这个是每轮循环找出最大值

   def OneHeapSort(list, l, r):
    if r-l<=0:
    return
    else:
    middle = l + (r-l-1)//2
    OneHeapSort(list, l, middle)
    OneHeapSort(list, middle+1, r)
    if list[middle]>list[r]:
    list[middle],list[r] = list[r],list[middle]
   # 依次将最大值放到数组的后面
   def heapSort(list):
    for i in range(len(list)-1, 0, -1):
    OneHeapSort(list, 0, i)
   list = [1, 10, 8, 200, 50, 4]
   heapSort(list)
   print(list) # [1,4,8,10,50,200]

   noname

   ZHK***[email protected]

   6年前 (2020年08月26日)
4. #0

   hhhhhh

   242***[email protected]

   10

   作为一个菜鸟,感觉源代码的注释写得太少了,以下做点注解吧。

   关键有3个点:

   1、先把堆调成小根堆的状态,方法是在每个结点的所有根部中确定它的位置;

   2、heapify函数实际上是对传入的arr[i]点在其所有根部中确定它的位置;

   3、堆头与堆尾交换,此后堆尾退出堆,堆的范围缩小1,公式中i即为堆的长度,之后再将新到堆首的点放在合适的位置,因为其他点均已在正确的位置上,其他点最多与新点交换一次。

   def heapify(arr, n, i): 
    largest = i 
    l = 2 * i + 1 # left = 2*i + 1 
    r = 2 * i + 2 # right = 2*i + 2 
    
    if l < n and arr[i] < arr[l]: 
    largest = l 
    
    if r < n and arr[largest] < arr[r]: 
    largest = r 
    
    if largest != i: 
    arr[i],arr[largest] = arr[largest],arr[i] # 交换
    # 此时largest位置的数字(也就是最开始输入那个lis[i])处于待定状态,需要在它所有根部中确定其位置
    heapify(arr, n, largest) 
    
   def heapSort(arr): 
    n = len(arr) 
    
    # Build a maxheap. 
    for i in range(n, -1, -1): 
    # 先把堆调整好小根堆的状态,在全堆中逐个调整每个数字的位置,调整的方法是在它所有根部中确定其位置
    heapify(arr, n, i) 
    
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
    arr[i], arr[0] = arr[0], arr[i] # 交换
    # 把新上来的0号安排到合适的位置上去,其中i指的是要调整的堆的范围
    heapify(arr, i, 0) 
   

   hhhhhh

   242***[email protected]

   6年前 (2020年10月26日)
5. #0

   秋风的阐明

   276***[email protected]

   参考地址

   0

   进行堆排序(大根堆)主要解决以下问题:

   • 1)构造大根堆;
   • 2)交换堆顶元素和最小值;
   • 3)重复 2

   def help_adjust(L,start,end):
    temp=L[start]
    i=start
    j=2*i
    while j<=end: # 这里一定要有等于
    if j<end and L[j]<L[j+1]: # 保证右子树小于左子树
    j+=1
    if temp<L[j]: # 根节点大于左子树
    L[i]=L[j]
    i=j
    j=2*i
    else:
    break
    L[i]=temp
   # 交换堆中元素
   def swap_param(L,i,j):
    L[i],L[j]=L[j],L[i]
    return L
   def help_sort(L):
    L_length=len(L)-1 # 这里构造的无序列表在最左侧加了一个0用于更好的确定堆顶
    first_sort_count=L_length//2 # 构造辅助变量用于构造大根堆
    for i in range(first_sort_count):
    help_adjust(L,first_sort_count-i,L_length)
    
    for i in range(L_length-1):
    swap_param(L,1,L_length-i)
    help_adjust(L,1,L_length-i-1)
    return [L[i] for i in range(1,len(L))]

   秋风的阐明

   276***[email protected]

   参考地址

   5年前 (2021年08月02日)