[从头学数学] 第256节 Python实现数据结构：堆(Heap)

[工程师阿伟]正在和[机器小伟]一起研究[计算几何]]。

<span style="font-size:18px;">#
###
# @usage   堆(完全二叉树）
# @author  mw
# @date    2016年09月05日  星期一  09:49:33 
# @param
# @return
#
###
class Heap():
    def __init__(self):
        self.heap = [];

    def data(self):
        return self.heap;
        
    def buildFrom(self, aSequence):
        """aSequence is an instance of a sequence collection which
        understands the comparison operators. The elements of
        aSequence are copied into the heap and ordered to build
        a heap."""
        step = 0;
        for item in aSequence:
            self.heappush(item);
            step += 1;
            print(step, '-->', str(self.data()));
        
    def heappush(self, item):
        """Push item onto heap, maintaining the heap invariant."""
        self.heap.append(item)
        Heap.__siftdown(self.heap, 0, len(self.heap)-1)


    def heappop(self):
        """Pop the smallest item off the heap, maintaining the heap invariant."""
        try:
            lastelt = self.heap.pop()    # raises appropriate IndexError if heap is empty
        except IndexError:
            lastelt = None;
        
        if self.heap:
            returnitem = self.heap[0]
            self.heap[0] = lastelt
            Heap.__siftup(self.heap, 0)
        else:
            returnitem = lastelt
        return returnitem

    def heapreplace(self, item):
        """Pop and return the current smallest value, and add the new item.

        This is more efficient than heappop() followed by heappush(), and can be
        more appropriate when using a fixed-size heap.  Note that the value
        returned may be larger than item!  That constrains reasonable uses of
        this routine unless written as part of a conditional replacement:

            if item > heap[0]:
                item = heapreplace(heap, item)
        """
        try:
            returnitem = self.heap[0]    # raises appropriate IndexError if heap is empty
        except IndexError:
            returnitem = None;
        
        self.heap[0] = item
        Heap.__siftup(self.heap, 0)
        return returnitem

    def heappushpop(self, item):
        """Fast version of a heappush followed by a heappop."""
        if self.heap and self.heap[0] < item:
            item, self.heap[0] = self.heap[0], item
            Heap.__siftup(self.heap, 0)
        return item

    # 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
    # is the index of a leaf with a possibly out-of-order value.  Restore the
    # heap invariant.
    def __siftdown(heap, startpos, pos):
        '''fromIndex is the index of an element in the heap.
        Pre: data[fromIndex..lastIndex] satisfies the heap condition,
        except perhaps for the element data[fromIndex].
        Post: That element is sifted down as far as neccessary to
        maintain the heap structure for data[fromIndex..lastIndex].'''
        newitem = heap[pos]
        # Follow the path to the root, moving parents down until finding a place
        # newitem fits.
        while pos > startpos:
            parentpos = (pos - 1) >> 1
            parent = heap[parentpos]
            if newitem > parent: #这个符号改变可变换大小排序，要同时改
                heap[pos] = parent
                pos = parentpos
                continue
            break
        heap[pos] = newitem

    def __siftup(heap, pos):
        '''childIndex is the index of a node in the heap. This method sifts
        that node up as far as necessary to ensure that the path to the root
        satisfies the heap condition. '''
        endpos = len(heap)
        startpos = pos
        newitem = heap[pos]
        # Bubble up the smaller child until hitting a leaf.
        childpos = 2*pos + 1    # leftmost child position
        while childpos < endpos:
            # Set childpos to index of smaller child.
            rightpos = childpos + 1
            if rightpos < endpos and not heap[childpos] > heap[rightpos]: #这个符号改变可变换大小排序，要同时改
                childpos = rightpos
            # Move the smaller child up.
            heap[pos] = heap[childpos]
            pos = childpos
            childpos = 2*pos + 1
        # The leaf at pos is empty now.  Put newitem there, and bubble it up
        # to its final resting place (by sifting its parents down).
        heap[pos] = newitem
        Heap.__siftdown(heap, startpos, pos)

    #某元素的父结点
    def parent(self, item):
        if item not in self.heap:
            return [None, -1]; #父结点值和序号
        else:
            index = self.heap.index(item);
            parentIndex = (index-1)>>1;
            if (parentIndex >= 0):
                parentValue = self.heap[parentIndex];
            else:
                parentValue = None;
            return [parentValue, parentIndex];

        


if __name__ == '__main__':
    h = Heap();

    data = [70, 30, 25, 90, 15, 85, 35, 87, 100]
    h.buildFrom(data);
    print(h.data());

    print(h.parent(70));
    print(h.parent(100));
    print(h.parent(101));
    print(h.parent(90));
    print(h.parent(15));

    sort = []
    while h.data():
        sort.append(h.heappop())
    print(sort)
#</span>

<span style="font-size:18px;">#
if __name__ == '__main__':
    h = Heap();

    data = [27, 58, 17, 12, 110, 98, 85, 34,  78]
    h.buildFrom(data);
    print(h.data());

    sort = []
    while h.data():
        sort.append(h.heappop())
    print(sort)
	
if __name__ == '__main__':
    h = Heap();

    data = [27, 58, 17, 12, 110, 98, 85, 34,  78, 71, 101, 36, 15, 27]
    h.buildFrom(data);
    print(h.data());

    sort = []
    while h.data():
        sort.append(h.heappop())
    print(sort)
	
>>> 
1 --> [37]
2 --> [45, 37]
3 --> [91, 37, 45]
4 --> [91, 37, 45, 5]
5 --> [91, 57, 45, 5, 37]
6 --> [91, 57, 74, 5, 37, 45]
7 --> [91, 57, 83, 5, 37, 45, 74]
8 --> [91, 57, 83, 45, 37, 45, 74, 5]
9 --> [99, 91, 83, 57, 37, 45, 74, 5, 45]
[99, 91, 83, 57, 37, 45, 74, 5, 45]
[99, 91, 83, 74, 57, 45, 45, 37, 5]

if __name__ == '__main__':
    h = Heap();

    data = [37, 45, 91, 5, 57, 74, 83, 45, 99]
    h.buildFrom(data);
    print(h.data());

    sort = []
    while h.data():
        sort.append(h.heappop())
    print(sort)
	

//////////

1 --> [70]
2 --> [70, 30]
3 --> [70, 30, 25]
4 --> [90, 70, 25, 30]
5 --> [90, 70, 25, 30, 15]
6 --> [90, 70, 85, 30, 15, 25]
7 --> [90, 70, 85, 30, 15, 25, 35]
8 --> [90, 87, 85, 70, 15, 25, 35, 30]
9 --> [100, 90, 85, 87, 15, 25, 35, 30, 70]
[100, 90, 85, 87, 15, 25, 35, 30, 70]
[87, 3]
[None, -1]
[None, -1]
[100, 0]
[90, 1]
[100, 90, 87, 85, 70, 35, 30, 25, 15]

if __name__ == '__main__':
    h = Heap();

    data = [70, 30, 25, 90, 15, 85, 35, 87, 100]
    h.buildFrom(data);
    print(h.data());

    print(h.parent(70));
    print(h.parent(100));
    print(h.parent(101));
    print(h.parent(90));
    print(h.parent(15));

    sort = []
    while h.data():
        sort.append(h.heappop())
    print(sort)
#</span>