python实现高级算法与数据结构:如何实现搜索引擎的竞价排名2
python实现高级算法与数据结构:如何实现搜索引擎的竞价排名2
接上一篇内容，我们继续完善堆的相关操作实现。下面我们要看的是堆的插入操作，当添加一个新元素时，我们把它加到数组末尾，此时新加入的元素必然是一个叶子节点，然后使用bubble_up对堆进行调整，相关代码实现如下：
elements = [ Element('a', 1), Element('a', 8), Element('a', 5), Element('a', 7),
Element('a', 2), Element('a', 4), Element('a', 3), Element('a', 6)
]
push_down(elements)
def insert(elements : [Element], elem_insert : Element):
elements.append(elem_insert)
bubble_up(elements, len(elements) - 1)
elem = Element('a', 10)
insert(elements, elem)
print(elements)
这里代码接上一节末尾代码，push_down先把给定元素数组调整到符合规则的堆，insert函数用于往堆里插入节点，它首先把节点放到数组末尾，然后调用bubbole_up调整新加入数组的元素位置，代码加入一个新元素，其优先级为10，因此加入后它应该变成根节点，代码运行后结果如下：
[Element('a', 10), Element('a', 8), Element('a', 5), Element('a', 7), Element('a', 2),
Element('a', 4), Element('a', 3), Element('a', 1), Element('a', 6)]
从输出看，新加入节点被调整到了正确位置。接着我们看另一个操作top，它把堆顶部元素弹出来。在根节点从堆中被挪走后，我们需要重新选择一个节点作为根节点，具体做法是，将数组中最后那个元素作为根节点，但这样可能会破坏堆的性质，也就是根节点必须是所有元素最大值，这时我们就可以调用push_down对它进行调整，代码如下：
def top(elements : [Element]):
if len(elements) == 0:
raise ValueError("Heap is empty")
last_element : Element = elements.pop()
if len(elements) == 0:
return last_element
else:
top_element : Element = elements.pop(0)
elements.insert(0, last_element)
push_down(elements, 0)
return top_element
def peek(elements : [Element]):
if len(elements) == 0:
raise ValueError("Heap is empty")
peek_top_element : Element = copy.deepcopy(elements[0])
return peek_top_element
top_element = top(elements)
print("top of heap is : ", top_element)
print("heap after top: ", elements)
调用top的代码接着前面的insert，执行上面代码后输出结果如下：
peek top element: Element('a', 10)
top of heap is : Element('a', 10)
heap after top: [Element('a', 8), Element('a', 7), Element('a', 5), Element('a', 6), Element('a', 2), Element('a', 4), Element('a', 3), Element('a', 1)]
代码实现中的peek仅仅把根节点的信息返回而没有将其从堆中去除，因此逻辑比较简单。下面我们看看元素的更新操作，当一个元素的优先级发生变化后，堆的性质可能会被破坏，元素的值如果变大了，那么我们需要调用bubble_up来进行调整，如果是变小了，我们可能需要调用push_down进行调整，代码实现如下：
def find(elements : [Element], content : str) -> int:
for idx, element in enumerate(elements):
if element.content == content:
return idx
return -1
def update(elements : [Element], content : str, new_priority : int):
idx : int = find(elements, content)
if idx >= 0:
old_priority = elements[idx].priority
elements[idx].priority = new_priority
if new_priority < old_priority:
push_down(elements, idx)
elif new_priority > old_priority:
bubble_up(elements, idx)
elements = [Element('a', 8), Element('b', 7), Element('c', 5),
Element('d', 6), Element('e', 2), Element('f', 4),
Element('g', 3), Element('h', 1)]
update(elements, "g", 9)
print("elements after update: ", elements)
find函数作用是根据给定内容查找对应元素，update函数实现中先查找，看数组中是否包含给定元素，如果存在则找到它对应数组下标， 然后判断元素对应的优先级是增大了还是减小了，如果增大了，那么使用bubble_up调整它与父节点，如果减小了，使用push_down调整它与子节点。
在调用update函数前，先修改元素g对应的优先级，然后使用update调整堆，由于我们把元素g的优先级调整到最大，因此update后，它应该作为堆的根节点，上面代码运行后结果如下：
[Element('g', 9), Element('b', 7), Element('a', 8), Element('d', 6), Element('e', 2), Element('f', 4), Element('c', 5), Element('h', 1)]`
从结果上看，update的实现逻辑基本上是正确的。接下来我们看，如果给一个随机数组，我们如何将它构建成一个堆。从前面我们实现的push_down函数可以知道，如果堆的根节点优先级变小，那么调用push_down就能恢复堆的性质。对于一个数组，它后半部分的元素都对于叶子节点，因此他们本身就已经满足堆性质。
假设位于数组后半部分的元素下表为i,那么它对应的父节点下标为 int(i / 2)，如果父节点的优先级比它大，那么以父节点为根节点的堆满足条件，但如果父节点的优先级比它小，我们就执行push_down进行调整，于是给定一个随机数组，我们只要对数组前半部分的元素依次调用push_down即可，代码如下：
import math
def heapify(elements : [Element]):
for index in range(math.ceil(len(elements) / 2) , -1, -1):
push_down(elements, index)
elements = [ Element('a', 1), Element('a', 2), Element('a', 3), Element('a', 4),
Element('a', 5), Element('a', 6), Element('a', 7), Element('a', 8)
]
heapify(elements)
print("heapify: ", elements)
上面代码运行后结果如下：
heapify: [Element('a', 8), Element('a', 5), Element('a', 7), Element('a', 4), Element('a', 1), Element('a', 6), Element('a', 3), Element('a', 2)]
通过检验可以确定，输出的数组元素满足堆的性质。我们需要确认一下上面代码的时间复杂度，当堆的高度是h时，push_down运行所需要的复杂度是o(h)，那么高度为h的节点能有多少个呢？
从parent函数的实现可以看到，当一个元素下标为i时，其父节点对应下标为 i/2，由此可以判断，高度每增加1，元素的个数相对于原来高度元素的个数就得少一半。于是高度为h的节点，对应个数最多为 n/(2^h)个，由于每个这样的元素在执行push_down时对应时间为o(h)，因此高度为h的元素全都执行完push_down，对应时间就是 o( n/(2^h)*h)。由于h的值最大不会超过lg(n)，因此总共的时间复杂度为：
上面公式中，右边式子还可以简化一下：
因此heapify运行时间最多不过O(2n)，所以它对应线性复杂度的时间。有了以上理论准备后，我们看看如何实现竞价排名，假设一个关键词对应一百万个网页，但是首页最多能显示十个链接，我们如何快速将优先级最高的链接选出来呢。
通常做法就是先排序，然后选出最后十个元素，快速排序的复杂度是O(n*lg(n))，当n为一百万时，lg(n)约等于20，于是总共需要两千万次运算。反之，我们将一百万个网页中的前10个构建一个小堆，（注意这里与我们前面描述的大堆不一样，不过我们只要将元素值取负值，然后按照大堆的操作就可以得到小堆。），然后从第11个开始，用每个元素与堆的头结点元素进行比较，如果元素的优先级大于小堆的头结点，那么我们一定能确定，小堆头结点对应的元素一定不再前10个元素范围内，于是我们把堆的头结点去除，将新的节点插入，这样遍历一次所有元素后，堆中的元素就是我们需要的元素。
这种做法时间复杂度为O(n*lg(k) + k*lg(k))，因为k是一个常值，因此nlg(k)等价于O(n)，于是这么做的时间复杂度就是o(n + k\lg(k))，于是一百万个网页，其运算效率也就一百万次左右，相对于前面做法的两千万次运算，其在效率上的改进是相当明显，特别是随着n值得增大，同时k值远远小于n值时，效率的提升就是本质性的，感兴趣的读者可以自己尝试实现一下。
请点击->更多精彩内容
腾讯云开发者
