min-max heap、つまり、最小値と最大値を見つけることが一定の操作であるヒープを作成しました。クラスのテストを作成したいので、ヒープが最小最大ヒープかどうかをチェックする関数を実装することにしました。ここにありますが、100% 正しいかどうかはわかりません。
def is_min_max_heap(h):
if not isinstance(h, MinMaxHeap):
return False
if h.heap:
for item in h.heap:
if not isinstance(item, HeapNode):
return False
for i, item in reversed(list(enumerate(h.heap))):
g = h.grandparent_index(i)
if g is not None:
if h.is_on_even_level(i):
if h.heap[g] > item:
return False
else:
if h.heap[g] < item:
return False
return True
このヒープの要素は class で表されることに注意してください。そのため、そのクラスのオブジェクトのみが含まれているHeapNodeかどうかを確認しています。self.heap偶数レベルは、たとえば 0、2、4 などです。このヒープの最小値は にありますself.heap[0]。最大値はmax(self.heap[1], self.heap[2])(両方が存在する場合) です。ノードの祖父母が存在しない場合にh.grandparent_index(i)返します。Nonei
私のアルゴリズムのアイデアはとてもシンプルです。下から始めて、奇数レベルの偶数かどうかを確認します。偶数レベルの場合、要素がその祖父母よりも大きいことを確認する必要があります。私が奇妙なレベルにいる場合は、祖父母よりも小さいことを確認する必要があります.
私のアルゴリズムは正しいですか？私はいくつかのポイントを逃していますか？それが正しければ、それを改善するための提案は十分に受け入れられます。
最終的に、私の実装は他の誰かにとって役立つかもしれません。
編集 1
私の関数は、偶数 (およびそれぞれ奇数) レベルの要素が互いに正しく配置されているかどうかをチェックしますが、最大要素が または で見つかったかどうか、self.heap[1]およびself.heap[2]最小要素が であるかどうかはチェックしないことに気付きましたself.heap[0]。
編集 2
編集1と@goCardsの回答に従って、新しい更新されたコードを追加しています。
def is_min_max_heap(h) -> bool:
"""Returns `True` if `h` is a valid `MinMaxHeap` object. `False` otherwise."""
if not isinstance(h, MinMaxHeap):
return False
if h.heap:
for item in h.heap:
if not isinstance(item, HeapNode):
return False
if h.size() == 1:
return True
if h.size() == 2:
return max(h.heap) == h.heap[1] and min(h.heap) == h.heap[0]
if h.size() >= 3:
if (h.heap[0] != min(h.heap) or
(h.heap[1] != max(h.heap) and
h.heap[2] != max(h.heap))):
return False
for i, item in reversed(list(enumerate(h.heap))):
p = h.parent_index(i)
if p != -1:
if h.is_on_even_level(i):
if h.heap[p] < item:
return False
else:
if h.heap[p] > item:
return False
g = h.grandparent_index(i)
if g != -1:
if h.is_on_even_level(i):
if h.heap[g] > item:
return False
else:
if h.heap[g] < item:
return False
return True