heap函数python,heap例句

python的 del 函数是删对象还是删引用

1.首先介绍下python的对象引用

1）Python中不存在传值调用，一切传递的都是对象引用，也可以认为是传址调用。即Python不允许程序员选择采用传值或传引用。Python参数传递采用的是“传对象引用”的方式。实际上，这种方式相当于传值和传引用的一种综合。如果函数参数收到的是一个可变对象（比如字典或者列表）的引用，就能修改对象的原始值——相当于通过“传引用”来传递对象。如果函数收到的是一个不可变对象（比如数字、字符或者元组）的引用，就不能直接修改原始对象——相当于通过"传值"来传递对象。

2）当复制列表或字典时，就复制了对象列表的引用，如果改变引用的值，则修改了原始的参数。

3）为了简化内存管理，Python通过引用计数机制实现自动垃圾回收功能，Python中的每个对象都有一个引用计数，用来计数该对象在不同场所分别被引用了多少次。每当引用一次Python对象，相应的引用计数就增1，每当消毁一次Python对象，则相应的引用就减1，只有当引用计数为零时，才真正从内存中删除Python对象。

2. 可变对象与不可变对象的概念与分类

Python在heap中分配的对象分成2类：

不可变对象（immutable object）：Number（int、float、bool、complex）、String、Tuple. 采用等效于“传引用”的方式。

可变对象（mutable object）：List、dictionary.采用等效于“传值”的方式。

3. del 是删除引用而不是删除对象，对象由自动垃圾回收机制（GC）删除

看这个例子：

x = 1

del x x

Traceback (most recent call last):

File "pyshell#28", line 1, in module

x

NameError: name 'x' is not defined x = ['Hello','world'] y = x y

['Hello', 'world'] x

['Hello', 'world'] del x x

Traceback (most recent call last):

File "pyshell#32", line 1, in modulex

NameError: name 'x' is not defined y

['Hello', 'world']

可以看到x和y指向同一个列表，但是删除x后，y并没有受到影响。这是为什么呢？

The reason for this is that you only delete the name,not the list itself,In fact ,there is no way to delete values in python(and you don’t really need to because the python interpreter does it by itself whenever you don’t use the value anymore)

举个例子，一个数据（比如例子中的列表），就是一个盒子，我们把它赋给一个变量x，就是好像把一个标签x贴到了盒子上，然后又贴上了y，用它们来代表这个数据，但是用del删除这个变量x就像是把标有x的标签给撕了，剩下了y的标签。

再看一个例子：

shoplist = ['apple', 'mango', 'carrot', 'banana']print ('The first item I will buy is', shoplist[0])

olditem = shoplist[0]del shoplist[0]  #del的是引用，而不是对象print ('I bought the',olditem)print ('My shopping list is now', shoplist)print(shoplist[0])

结果为：

The first item I will buy is apple

I bought the apple

My shopping list is now ['mango', 'carrot', 'banana']

mango

实例补充：

#!/usr/bin/evn python# -*- coding:utf-8 -*-# Author: antcolonies'''python中的内置方法del不同于C语言中的free和C++中的delete

（free和delete直接回收内存，当然存储于该内存的对象也就挂了）

Python都是引用，垃圾回收为GC机制'''

'''if __name__ == '__main__':

a = 1          # 对象 1 被 变量a引用，对象1的引用计数器为1

b = a          # 对象1 被变量b引用，对象1的引用计数器加1

c = a          # 对象1 被变量c引用，对象1的引用计数器加1

del a          # 删除变量a，解除a对1的引用，对象1的引用计数器减1

del b          # 删除变量b，解除b对1的引用，对象1的引用计数器减1

print(c)       # 1'''

if __name__=='__main__':

li=['one','two','three','four','five']  # 列表本身不包含数据'one','two','three','four','five'，而是包含变量：li[0] li[1] li[2] li[3] li[4]

first=li[0]       # 拷贝列表，也不会有数据对象的复制，而是创建新的变量引用

del li[0]    print(li)         # ['two','three','four','five']

print(first)      # one

list1 = li    del li    print(list1)      # ['two', 'three', 'four', 'five']#   print(type(li))   # NameError: name 'li' is not defined

Python高级数据结构——堆

在一个 最小堆 (min heap) 中，如果 P 是 C 的一个父级节点，那么 P 的 key（或 value) 应小于或等于 C 的对应值。 正因为此，堆顶元素一定是最小的，我们会利用这个特点求最小值或者第 k 小的值。

在一个 最大堆 (max heap) 中，P 的 key（或 value) 大于或等于 C 的对应值。

以python为例，说明堆的几个常见操作，这里需要用到一个内置的包：heapq

python中使用堆是通过传入一个数组，然后调用一个函数，在原地让传入的数据具备堆的特性

需要注意的是，heapify默认构造的是小顶堆（min heap），如果要构造大顶堆，思路是把所有的数值倒转，既* -1，例如：

使用heapq提供的函数： heappop 来实现

具体使用方式参考 初始化Heapify

使用heapq提供的函数： heappush 来实现

同时heapq还提供另外一个函数： heappushpop ，能够在一个函数实现pushpop两个操作；顺序是：先push再pop

根据官方文档的描述，这个函数会比先在外围先调用heappush，再调用heappop，效率更高

先pop数据再push数据，和heappushpop的顺序是反着的； 同样的，这样调用的性能也会比先调用heappop再调用heappush更好

如果pop的时候队列是空的，会抛出一个异常

可以通过 heapq.merge 将多个 已排序 的输入合并为一个已排序的输出，这个本质上不是堆；其实就是用两个指针迭代

对于这个问题，有一个算法题可以实现相同的功能

从 iterable 所定义的数据集中返回前 n 个最大/小元素组成的列表。

函数为： heapq.nlargest() | heapq.nsmallest()

heapq - Heap queue algorithm - Python 3.10.4 documentation

python几种经典排序方法的实现

class SortMethod:

'''

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

插入算法把要排序的数组分成两部分：

第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）

第二部分就只包含这一个元素（即待插入元素）。

在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

'''

def insert_sort(lists):

# 插入排序

count = len(lists)

for i in range(1, count):

key = lists[i]

j = i - 1

while j = 0:

if lists[j] key:

lists[j + 1] = lists[j]

lists[j] = key

j -= 1

return lists

'''

希尔排序 (Shell Sort) 是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL．Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

'''

def shell_sort(lists):

# 希尔排序

count = len(lists)

step = 2

group = count / step

while group 0:

for i in range(0, group):

j = i + group

while j count:

k = j - group

key = lists[j]

while k = 0:

if lists[k] key:

lists[k + group] = lists[k]

lists[k] = key

k -= group

j += group

group /= step

return lists

'''

冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

'''

def bubble_sort(lists):

# 冒泡排序

count = len(lists)

for i in range(0, count):

for j in range(i + 1, count):

if lists[i] lists[j]:

temp = lists[j]

lists[j] = lists[i]

lists[i] = temp

return lists

'''

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

'''

def quick_sort(lists, left, right):

# 快速排序

if left = right:

return lists

key = lists[left]

low = left

high = right

while left right:

while left right and lists[right] = key:

right -= 1

lists[left] = lists[right]

while left right and lists[left] = key:

left += 1

lists[right] = lists[left]

lists[right] = key

quick_sort(lists, low, left - 1)

quick_sort(lists, left + 1, high)

return lists

'''

直接选择排序

第 1 趟，在待排序记录 r[1] ~ r[n] 中选出最小的记录，将它与 r[1] 交换；

第 2 趟，在待排序记录 r[2] ~ r[n] 中选出最小的记录，将它与 r[2] 交换；

以此类推，第 i 趟在待排序记录 r[i] ~ r[n] 中选出最小的记录，将它与 r[i] 交换，使有序序列不断增长直到全部排序完毕。

'''

def select_sort(lists):

# 选择排序

count = len(lists)

for i in range(0, count):

min = i

for j in range(i + 1, count):

if lists[min] lists[j]:

min = j

temp = lists[min]

lists[min] = lists[i]

lists[i] = temp

return lists

'''

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即 A[PARENT[i]] = A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

'''

# 调整堆

def adjust_heap(lists, i, size):

lchild = 2 * i + 1

rchild = 2 * i + 2

max = i

if i size / 2:

if lchild size and lists[lchild] lists[max]:

max = lchild

if rchild size and lists[rchild] lists[max]:

max = rchild

if max != i:

lists[max], lists[i] = lists[i], lists[max]

adjust_heap(lists, max, size)

# 创建堆

def build_heap(lists, size):

for i in range(0, (size/2))[::-1]:

adjust_heap(lists, i, size)

# 堆排序

def heap_sort(lists):

size = len(lists)

build_heap(lists, size)

for i in range(0, size)[::-1]:

lists[0], lists[i] = lists[i], lists[0]

adjust_heap(lists, 0, i)

'''

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （Divide and Conquer） 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：

比较 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，则将第一个有序表中的元素 a[i] 复制到 r[k] 中，并令 i 和 k 分别加上 1；

否则将第二个有序表中的元素 a[j] 复制到 r[k] 中，并令 j 和 k 分别加上 1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。归并排序的算法我们通常用递归实现，先把待排序区间 [s,t] 以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t]。

'''

def merge(left, right):

i, j = 0, 0

result = []

while i len(left) and j len(right):

if left[i] = right[j]:

result.append(left[i])

i += 1

else:

result.append(right[j])

j += 1

result += left[i:]

result += right[j:]

return result

def merge_sort(lists):

# 归并排序

if len(lists) = 1:

return lists

num = len(lists) / 2

left = merge_sort(lists[:num])

right = merge_sort(lists[num:])

return merge(left, right)

'''

基数排序 （radix sort） 属于“分配式排序” （distribution sort），又称“桶子法” （bucket sort） 或 bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序。

其时间复杂度为 O (nlog(r)m)，其中 r 为所采取的基数，而 m 为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

'''

import math

def radix_sort(lists, radix=10):

k = int(math.ceil(math.log(max(lists), radix)))

bucket = [[] for i in range(radix)]

for i in range(1, k+1):

for j in lists:

bucket[j/(radix**(i-1)) % (radix**i)].append(j)

del lists[:]

for z in bucket:

lists += z

del z[:]

return lists

---------------------

作者：CRazyDOgen

来源：CSDN

原文：

版权声明：本文为博主原创文章，转载请附上博文链接！