더미 정렬 - python
1496 단어 정렬 알고리즘
데이터 구조 - 더미, 다음 과 같은 성질 을 가지 고 있 습 니 다.
parent(i): math.floor(i/2)
left(i): 2*i
right(i): 2*i+1
더 미 는 최대 더미 (A [parent (i)] > = A [i]) 와 최소 더미 (A [parent (i)] < = A [i]) 로 나 눌 수 있다.일반적으로 가장 많은 무 더 기 는 정렬 알고리즘 에 사용 되 고, 가장 작은 무 더 기 는 우선 대기 열 에 사용 된다.
heapSort 알고리즘 구현:
Max_hepify: 가장 많은 성질 을 유지 합 니 다.
Build_Max_heap ： 구조 최대 더미.
배열 을 최대 더미 로 변환 합 니 다. 우 리 는 잎 노드 가 하나의 요 소 를 포함 하 는 더미 라 고 생각 할 수 있 습 니 다. 따라서 다른 비 잎 노드 에 Max 를 호출 하면 됩 니 다.heapify。
heapSort: 쌓 기 정렬 (원래 주소).
먼저 배열 을 최대 더미 로 바 꾸 고 배열 의 최대 치 는 반드시 가장 많은 더미 의 꼭대기 가 되 기 때문에 A [1] 와 A [n] 를 대조 한 다음 에 Max 를 호출 해 야 합 니 다.hepify, 이 과정 을 반복 하면 원래 주소 정렬 을 실현 할 수 있 습 니 다.
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WEEK. 01 2022.04.03 TIL정렬(sorting)이란 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 의미함. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
