python 에서 두 갈래 더미 와 더미 정렬 을 실현 하 는 예시
3704 단어 더미 정렬python두 갈래 로 된 더미
더 미 는 큰 머리 더미 와 작은 머리 더미 로 나 뉘 는데 그 이름 처럼 큰 머리 더미 의 첫 번 째 요 소 는 가장 크 고 모든 하위 노드 가 있 는 부모 노드 는 그 데이터 값 이 아들 노드 의 값 보다 크다.작은 머리 더 미 는 반대 다.
나 는 다음 나무 더 미 를 만 드 는 알고리즘 과정 을 대충 설명 한다.
N/2 위치의 배열 데 이 터 를 찾 습 니 다.이 위치 에서 이 노드 의 왼쪽 자 결점 의 색인 을 찾 습 니 다.먼저 이 결점 의 아래 자 결점 을 비교 하고 가장 큰 자 결점 의 색인 을 왼쪽 자 결점 에 할당 한 다음 에 가장 큰 자 결점 과 부 결점 을 비교 합 니 다.만약 에 부 결점 보다 크 면 부 노드 와 데 이 터 를 교환 합 니 다.물론 실현 을 대충 말 했 을 뿐 이 과정 에서 결점 이 존재 하지 않 는 상황 을 고려 해 야 한다.
코드 보기:
#
def binaryHeap(arr, lenth, m):
temp = arr[m] #
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp
def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1
print(" :")
print(arr) #
if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]
heapsort(arr, len(arr))
쌓 기 정렬 과정 은 마지막 노드 와 첫 번 째 노드 를 순서대로 비교 교환 하 는 것 이다.
#
def binaryHeap(arr, lenth, m):
temp = arr[m] #
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp
def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1
print(" :")
print(arr) #
i = length-1
while(i > 0):
arr[i], arr[0] = arr[0], arr[i] #
binaryHeap(arr, i, 0)
i = i - 1560
def pop(arr):
first = arr.pop(0)
return first
if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]
heapsort(arr, len(arr))
print(" ")
print(arr) #
data = pop(arr)
print(data)
print(arr)
python 은 모듈 을 봉 인 했 습 니 다.우 리 는 이 모듈 을 사용 하면 우선 대기 열 을 효율적으로 실현 할 수 있 습 니 다.
import heapq
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item)) #
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1] #
if __name__ == '__main__':
p = PriorityQueue()
p.push(Item('foo'), 1)
p.push(Item('bar'), 5)
p.push(Item('spam'), 4)
p.push(Item('grok'), 1)
print(p.pop())
print(p.pop())
구체 적 으로 보 세 요hepq 홈 페이지이상 의 python 에서 이 진 더미 와 쌓 기 순 서 를 실현 하 는 예 는 바로 편집장 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 께 참고 가 되 고 저희 도 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
석 주 - 데이터 구조 - 선택 & 쌓 기 정렬예전 에 내 가 가장 좋아 했 던 것 은 순 서 를 선택 하 는 것 이 었 다. 현재 요소 의 뒤에서 가장 작은 요 소 를 선택 하여 교환 하 는 것 이다. 쌓 기 정렬 은 빠 른 정렬 의 개선 으로 거품 처럼 빠르...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.