Though Dan Lowe's excellent answer very thoroughly answered the OP's question about the difference between PUT and PATCH, its answer to the question of why PATCH is not idempotent is not quite correct.
To show why PATCH isn't idempotent, it helps to start with the definition of idempotence (from Wikipedia):
The term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times [...] An idempotent function is one that has the property f(f(x)) = f(x) for any value x.
In more accessible language, an idempotent PATCH could be defined as: After PATCHing a resource with a patch document, all subsequent PATCH calls to the same resource with the same patch document will not change the resource.
Conversely, a non-idempotent operation is one where f(f(x)) != f(x), which for PATCH could be stated as: After PATCHing a resource with a patch document, subsequent PATCH calls to the same resource with the same patch document do change the resource.
To illustrate a non-idempotent PATCH, suppose there is a /users resource, and suppose that calling GET /users returns a list of users, currently:
[{ "id": 1, "username": "firstuser", "email": "[email protected]" }]
Rather than PATCHing /users/{id}, as in the OP's example, suppose the server allows PATCHing /users. Let's issue this PATCH request:
PATCH /users
[{ "op": "add", "username": "newuser", "email": "[email protected]" }]
Our patch document instructs the server to add a new user called newuser to the list of users. After calling this the first time, GET /users would return:
[{ "id": 1, "username": "firstuser", "email": "[email protected]" },
{ "id": 2, "username": "newuser", "email": "[email protected]" }]
Now, if we issue the exact same PATCH request as above, what happens? (For the sake of this example, let's assume that the /users resource allows duplicate usernames.) The "op" is "add", so a new user is added to the list, and a subsequent GET /users returns:
[{ "id": 1, "username": "firstuser", "email": "[email protected]" },
{ "id": 2, "username": "newuser", "email": "[email protected]" },
{ "id": 3, "username": "newuser", "email": "[email protected]" }]
The /users resource has changed again, even though we issued the exact same PATCH against the exact same endpoint. If our PATCH is f(x), f(f(x)) is not the same as f(x), and therefore, this particular PATCH is not idempotent.
Although PATCH isn't guaranteed to be idempotent, there's nothing in the PATCH specification to prevent you from making all PATCH operations on your particular server idempotent. RFC 5789 even anticipates advantages from idempotent PATCH requests:
A PATCH request can be issued in such a way as to be idempotent, which also helps prevent bad outcomes from collisions between two PATCH requests on the same resource in a similar time frame.
In Dan's example, his PATCH operation is, in fact, idempotent. In that example, the /users/1 entity changed between our PATCH requests, but not because of our PATCH requests; it was actually the Post Office's different patch document that caused the zip code to change. The Post Office's different PATCH is a different operation; if our PATCH is f(x), the Post Office's PATCH is g(x). Idempotence states that f(f(f(x))) = f(x), but makes no guarantes about f(g(f(x))).