C++和Java等语言都有++和–操作,为什么以方便自居的Python却没有这种操作呢?

Python的数值对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a = 1
b = 1
c = 1000123
d = 1000123

print id(a)
print id(b)
print id(c)
print id(d)

## output:
# 94181316498840
# 94181316498840
# 94181323965720
# 94181323965720
  • Python数值对象都是不可变类型,与String一样,所以不能修改对象内部数据
  • C++中的i++修改内存中对象本身,数值增加1,而Python不能修改对象本身
  • 与C++中字符串可以修改,Python中不能修改是一个道理

本文介绍Python中优先队列的用法

  • 注意: queue并不能算是Python标准库,所以在LeetCode等OJ环境中不能使用, 想要使用优先队列的话可以使用Python的标准库heapq
  • heapq的使用请参考 Python——heapq模块-最大堆最小堆

导入包

1
2
3
from Queue import PriorityQueue
# or
from queue import PriorityQueue
  • queue包名已经弃用,测试发现本地Python2.7环境可以用,但是LeetCode线上环境不能用
  • 推荐使用Queue

使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Queue import PriorityQueue

pq = PriorityQueue()

pq.put((10, "start"))
pq.put((5, "b", 12, 123))
pq.put((5, "a", 6))
pq.put(1)
pq.put(4)
pq.put([0, "a"])
pq.put([8, "b"])
pq.put("avb")
pq.put(None)

# while pq.not_empty()
# while not pq.empty()
while pq.qsize():
    print pq.get()
## output:
# None
# 1
# 4
# [0, 'a']
# [8, 'b']
# avb
# (5, 'a', 6)
# (5, 'b', 12, 123)
# (10, 'start')

  • 不能使用not pq这样的语句判断优先队列是否收敛,他不是普通的内嵌对象(list,str等是内嵌对象),除非pq == None否则,双端队列对象永远为not pq == False

  • 下面用法最优:

    1
    while pq.qsize():

  • PriorityQueue中默认递增排序(这一点与Python中的sorted函数和sort()函数一样),每次get(),移除并返回最小的对象

  • PriorityQueue中,可以同时添加不同类别的对象

  • PriorityQueue会将对象首先按照类别排序,然后各个类别内部按照不同数值排序

  • 若传入对象是可以直接比较大小的类型即可直接传入,包括tuple, list, str, int(long)等类型

    • Python中list,tuple,str等都是可以直接比较大小的,默认使用他们的第一个元素比较大小,如果第一个元素相等,则比较第二个元素,以此类推
    • 详细情况参考本文后面的说明

Python中的内嵌对象比较大小

  • Python中类别间也可以比较大小,默认类别间大小为:tuple > str > list > int(long) > None, 但是记不清楚的话不建议使用Python的这个特性,容易造成错误
  • Python中list,tuple,str等都是可以直接比较大小的,默认使用他们的第一个元素比较大小,如果第一个元素相等,则比较第二个元素,以此类推
  • Python中类别间也可以比较大小,默认类别间大小为:tuple > str > list > int(long) > None, 但是记不清楚的话不建议使用Python的这个特性,容易造成错误
    1
    2
    3
    4
    5
    ls = [(1, 'b'), (1, 'a'), (2, 'a'), [1, 'a'], [1, 'b'], [2, 'a'], '1a', '1b', '2a', 1, 2, 3, None]
    ls.sort()
    print ls
    # # output
    # [None, 1, 2, 3, [1, 'a'], [1, 'b'], [2, 'a'], '1a', '1b', '2a', (1, 'a'), (1, 'b'), (2, 'a')]

Python自定义对象比较大小

  • 在做算法题时,没必要的情况下不建议使用

  • 在做工程时建议使用这种方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    import Queue
    class Node():
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val < other.val

    pq = Queue.PriorityQueue()
    pq.put(Node(5))
    pq.put(Node(1))

    while pq.qsize():
        print pq.get().val
    # # output
    # 1
    # 5

  • 注意__lt__函数中是小于号,说明递增排序,大于号,说明递减排序

  • PriorityQueue对象不是普通Python内嵌对象,不能使用Python内嵌的len函数