-1

以下是我所做的，但它不处理插入的最大要求。

如何给类一个最大值并在插入中检查它，然后删除最不重要的元素。然后找出实现中最不重要的元素是什么。

有一些问题试图解决这个问题。

import math
import random

class BinaryHeap:
def __init__(self, array, direction=1, size=100):
    if(size > len(array)):
        self.size = len(array)
    else:
        self.size = size;
    self.bBinaryHeap = array[:]
    if 0 < direction:
        self.compare = self.greater
    else:
        self.compare = self.less
    self.buildBinaryHeap()

def node(self, index):
    return (index << 1) + 1

def parent(self, index):
    return (index - 1) >> 1

def bBinaryHeapifyDown(self, index): 
    swap = self.bBinaryHeap[index]
    while self.node(index) < self.size:
        node = self.node(index)
        if node + 1 < self.size and self.compare(self.bBinaryHeap[node], self.bBinaryHeap[node + 1]) > 0:
            node += 1
        if self.compare(swap, self.bBinaryHeap[node]) > 0:
            self.bBinaryHeap[index] = self.bBinaryHeap[node];
        else:
            break
        index = node
    self.bBinaryHeap[index] = swap

def upheapify(self, index):  
    while 0 < index and self.compare(self.bBinaryHeap[index], self.bBinaryHeap[self.parent(index)]) < 0:
        parent = self.parent(index)
        swap = self.bBinaryHeap[parent]
        self.bBinaryHeap[parent] = self.bBinaryHeap[index]
        self.bBinaryHeap[index] = swap
        index = parent

def buildBinaryHeap(self):
    indices = range(0, int(self.size / 2))
    reversed(indices)
    for index in indices:
        self.bBinaryHeapifyDown(index)

def insert(self, value):
    self.shrink()
    index = self.size
    self.bBinaryHeap[index] = value
    self.size += 1
    self.upheapify(index)

def search(self, value):
    for index in range(self.size):
        if self.bBinaryHeap[index] == value:
            return index

def delete(self, value):
    index = self.search(value)
    self.size -= 1
    self.bBinaryHeap[index] = self.bBinaryHeap[self.size]
    parent = self.parent(index)
    if (index == 0) or (self.compare(self.bBinaryHeap[parent], self.bBinaryHeap[index]) < 0):
        self.bBinaryHeapifyDown(index)
    else:
        self.upheapify(index)

def shrink(self):
    capacity = len(self.bBinaryHeap)
    if capacity == self.size:
        self.bBinaryHeap.extend([0] * capacity)

def greater(self, value1, value2):
    if value1 == value2:
        return 0
    elif value1 < value2:
        return 1
    elif value1 > value2:
        return -1

def less(self, value1, value2):
    if value1 == value2:
        return 0
    elif value1 < value2:
        return -1
    elif value1 > value2:
        return 1

def getLevel(self, index):
    return int(math.floor(math.log(index + 1, 2)))

def displayBinaryHeap(self):
    printBinaryHeap = str(self.bBinaryHeap)
    height = self.getLevel(self.size)
    previous = -1
    for index in range(self.size):
        getLevel = self.getLevel(index)
        n = height - getLevel
        indent = int(math.pow(2, n + 1) - 2)
        spacing = 2 * indent
        if getLevel != previous:
            printBinaryHeap += '\n'
            printBinaryHeap += ' ' * indent
            previous = getLevel
        else:
            printBinaryHeap += ' ' * spacing
        printBinaryHeap += '%4d' % self.bBinaryHeap[index]
    print(printBinaryHeap)



if __name__ == "__main__":
size =10
array = [random.randint(0, 100) for i in range(size)]
bBinaryHeap = BinaryHeap(array, 1, 100)
print('Binary bBinaryHeap:')
bBinaryHeap.displayBinaryHeap()
4

1 回答 1

0

您的代码有许多缩进错误。在 python 中，缩进很重要。

至于这段代码：

if 0 < direction:
    self.compare = self.greater
else:
    self.compare = self.less

self.greater 和 self.less 不存在。你正在做相当于这个：

x = 大象

这很好，但除非您在该行之前将变量大象设置为某个值，否则这是一个错误。

我如何给班级一个最大值

class BinaryHeap:
    pass

BinaryHeap.max = 10
print(BinaryHeap.max)

--output:--
10

并在插入中检查它

class BinaryHeap:
    max = 10

    def insert(self):
        print(self.max)


bh = BinaryHeap()
bh.insert()

--output:--
10

然后删除最不重要的元素

x = 0b1111
print(x) #15

y = x >> 1
print("{:b}".format(y))  #111
print(y)  #7

然后找出实现中最不重要的元素是什么

x = 0b1110
print(x)  #=>14

b_str = "{:b}".format(x)
print(repr(b_str)) #=> '1110'

for direction in [1, -1]:
    if direction > 0:
        least_signif = b_str[-1]
    else:
        least_signif = b_str[0]

    print(least_signif)


--output:--
0
1
于 2015-12-06T23:47:29.893 回答