FilesExpand file tree

 master

/

BinaryHeap.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (52 loc) · 1.74 KB

 master

/

BinaryHeap.py

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (52 loc) · 1.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

# 构建树实现堆

class BinHeap:

def __init__(self):

self.heapList = [0]

self.currentSize = 0

#插入新结点后必要时交换子节点和父节点的位置保持堆的性质

def percUp(self, i):

while i//2 > 0:

if self.heapList[i] < self.heapList[i//2]:

temp = self.heapList[i//2]

self.heapList[i//2] = self.heapList[i]

self.heapList[i] = temp

i = i//2

# 插入节点

def insert(self, k):

self.heapList.append(k)

self.currentSize += 1

self.percUp(self.currentSize)

# 删除堆顶元素后, 交换堆尾和空堆顶的位置并实现元素的下沉

def percDown(self, i):

while (i*2) <= self.currentSize:

mc = self.minChild(i)

if self.heapList[i] > self.heapList[mc]:

temp = self.heapList[i]

self.heapList[i] = self.heapList[mc]

self.heapList[mc] = temp

i = mc

def minChild(self, i):

if i * 2 + 1 > self.currentSize:

return i * 2

else:

if self.heapList[i*2] < self.heapList[i*2+1]:

return i * 2

else:

return i * 2 + 1

def delMin(self):

retval = self.heapList[1]

self.heapList[1] = self.heapList[self.currentSize]

self.currentSize = self.currentSize - 1

self.heapList.pop()

self.percDown(1)

return retval

def buildHeap(self, alist):

i = len(alist) // 2

self.currentSize = len(alist)

self.heapList = [0] + alist[:]

while (i > 0):

self.percDown(i)

i = i - 1

return self.heapList

H = BinHeap()

print(H.buildHeap([9, 6, 5, 2, 3]))