为什么我的堆排序不起作用?

3
我有一个使用网上伪代码编写的Python堆排序代码。但它给出了错误的结果。
def heapSortUp(a):          
    heapifyUp(a, len(a))

    end = len(a)-1
    while end > 0:
        a[end], a[0] = a[0], a[end]
        end -= 1
        siftUp(a, 0, end)
    return a

def heapifyUp(a, count):
    end = 1

    while end < count:
        siftUp(a, 0, end)
        end += 1

def siftUp(a, start, end):
    child = end

    while child > start:
        parent = int(math.floor((child-1)/2))       # floor = abrunden

        if a[parent] < a[child]:
            a[parent], a[child] = a[child], a[parent]
            child = parent
        else:
            return

我特别希望使用siftUP版本。

通过计算print heapSortUp([1,5,4,2,9,8,7]), 它返回:[8, 7, 9, 2, 1, 4, 5, 7, 5]

2个回答

3
问题在于你需要在heapSortUp(a)中向下筛选而不是向上。
def heapSortUp(a):          
    heapifyUp(a, len(a))

    end = len(a)-1
    while end > 0:
        a[end], a[0] = a[0], a[end]
        end -= 1
        siftDown(a, 0, end)
    return a

你需要筛选下降的原因是因为向上筛选会使堆无效。这可以通过一个简单的例子来说明。

拿一个堆 4,3,2,1 举例。排序经过一次迭代后,你将把 4 放在末尾,把 1 放在前面。所以堆看起来像这样:

 1
3 2

然而,当你向上筛选时,你交换了12的位置。这意味着23优先级更高。如果按照原来的排序方式继续进行排序,你会得到数组1,3,2,4
要获得实际的排序结果,你需要向下筛选一次,使堆看起来像第一次迭代之后的样子。
 3
1 2

我将把siftDown的实现留给你。


1

对于升序堆排序,您可以使用以下代码:

def heapSort(a):
    count = len(a)
    heapify(a, count)

    end = count-1
    while end > 0:
        a[end], a[0] = a[0], a[end]
        end = end - 1
        siftDown(a, 0, end)


def heapify(a, count):
    start = math.floor((count - 1) / 2)

    while start >= 0:
        siftDown(a, start, count-1)
        start = start - 1

def siftDown(a, start, end):
    root = start

    while root * 2 + 1 <= end:
        child = root * 2 + 1
        swap = root
        if a[swap] < a[child]:
            swap = child
        if child+1 <= end and a[swap] < a[child+1]:
            swap = child + 1
        if swap != root:
            a[root], a[swap] = a[swap], a[root]
            root = swap
        else:
            return

或者您可以使用此代码:
def heapSortDown(lst):
  for start in range(math.floor((len(lst)-2)/2), -1, -1):
    sift(lst, start, len(lst)-1)

  for end in range(len(lst)-1, 0, -1):
    lst[end], lst[0] = lst[0], lst[end]
    sift(lst, 0, end - 1)
  return lst

def sift(lst, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and lst[child] < lst[child + 1]:
      child += 1
    if lst[root] < lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
    else:
      break

并且为降序:

def heapSortDown(lst):
  for start in range(math.floor((len(lst)-2)/2), -1, -1):
    sift(lst, start, len(lst)-1)

  for end in range(len(lst)-1, 0, -1):
    lst[end], lst[0] = lst[0], lst[end]
    sift(lst, 0, end - 1)
  return lst

def sift(lst, start, end):
  root = start
  while True:
    child = root * 2 + 1
    if child > end: break
    if child + 1 <= end and lst[child] > lst[child + 1]:
      child += 1
    if lst[root] > lst[child]:
      lst[root], lst[child] = lst[child], lst[root]
      root = child
    else:
      break

@hammar,我已经修复了堆排序的问题。 - Mehdi Yeganeh

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接